I’ve had some problems recently (the last couple of weeks) with Empathy on Ubuntu 10.04. All my MSN accounts just started giving my an “Authentication Failed”.

After checking with pidgin, which I use for other accounts, that my credentials were still working I found a post in the Ubuntu Forums that gave me a good solution:

$ sudo aptitude remove telepathy-butterfly
— Make sure you have telepathy-haze installed, if not
$ sudo aptitude install telepathy-haze
— Delete the accounts and recreate them with the new plugin

I’m not sure why this happened, but at least it’s working again.
Hope this helps someone else out there.