Did you make sure all your passwords are correct?
If so restart your phone. (Hold the lock button and home button till it turns off) That usually takes care of my problmes.
If that doesnt fix it, make sure your host name is correct. I believe it is "pop3.live.com" or something similar.