I am not certain but I believe all msn, live, hotmail, etc. Microsoft accounts should not be added as POP3 but rather as Exchange type (Microsoft Exchange instead of Other). Not that this explains why you were able to add your msn but not your live. That aside, I believe that Exchange type is better than POP3 type due to IMAP (IMAP Idle?).
My msn/live/hotmail accounts have always been a bit funky: I get periodic credentials/verify errors out of the blue -- yet they go away. Same with the msn/live IM apps (which are now no longer supported and all accounts migrated to Skype). I'd lean to something off on MS's end. My suggestion would be to log into your live account from your PC, change the password, then change it back and try again from your phone. Good luck.