I tried wiping my phone without reloading the databases, and loading .419 from scratch. Youmail will give an error while connecting everytime now. Its connection permissions are all set to allow, and there is no firewall.
I'm having the same problem. I thought it had something to do with my upgrade to OS 5 over the weekend, but everything else seems to be running as normal.