I have a RESTful login web service. However, there's been debate internally as to what status code is best to return in the case that a set of credentials passed to it aren't valid. I've been returning 401; but that doesn't seem correct as it implies you have to be logged in already to use the login service. 403 has also been discussed; but that implies you're already authenticated but are restricted from using a given resource. Maybe 404; because a user could not be found with said credentials.
What's the proper status code to return from a login service if the credentials aren't valid?
If it matters, this REST login API is being consumed by both a web app and an iPhone app.