You should throw up an "invalid email" error. It's the most transparent, communicates exactly what has happened, and the user can immediately adjust behaviour based on that feedback, with a low likelihood of seeing that same message again. Let me run through why the other options aren't a good idea:
Prompting to log in with the new address is a security anti-pattern. If I know your old email address, I can now discover what your new email address is given that I know you use service X. This could be a privacy concern, especially on for instance a dating site or social network. (Edit: this is only a problem if you actually display the new email address; I misread your bullet and thought that was what you were saying. The point still stands though :)
You don't know why the user is changing his/her email address, so it's risky to continue locking that email address to this account. For all you know they canceled their account with their previous email host and that address is now used by someone else who may also want to access your service (unlikely, but in theory!).
If you implement the "invalid email" warning, you can make things slightly friendlier using our trusty low-cost friend, Copywriting:
The email address or password you entered is invalid. [...] Perhaps you changed the email address you use to log in?
You could also offer the ability to request which email address is being used to log in. To do this without ending up with the abovementioned anti-pattern, allow the user to input his/her old email address and then display a message saying "we sent an email to the address we have on file that you're using to log in". Then the user will be able to remember which email address they're using by association from the email you send them. Of course, you need to doublecheck that users don't mind that you retain a log of their past email addresses - they may not appreciate it.
Edit: Clearly the best solution is a combination of your first and second points, which I neglected to read thoroughly before writing this answer. Most of the answer still makes sense, though.