You **have to go with the first option** (stating that the "username or password is invalid"), and this has nothing to do with security.

Let's say that I usually use JohnGB as my username, but on your service someone else has that username, so I use JohnGB123 instead.  Say I've then forgotten my username and I enter JohnGB as my username, but use my correct password.

Is that a correct password and incorrect username or a correct username and an incorrect password?

There is no such thing as having a correct username without its matching password, and no correct password without its matching username.  **Usernames and passwords only represent anything when used in combination**.