It sounded like something is not right with SRP and that's why I asked you if you used the same SRP as in BES 4.1.
If I was I I would have removed bes 5.o completally.
-Wait for new srp etc. from carrier and while waiting do following:
-Check permissions on new windows server (local server admin. logon as service,logon locally etc)
-If windows 2008 R1 or R2 disable IPv6 and firewall.
-check permissions of BESAdmin service account on exchange.
-Make sure your exchange 2010 hase latest rollup etc.
-Make sure you install latest cdo and mapi software.
-Read install guides
Once you receive SRPs etc do following:
-start install from scratch.
-Once done activate one test user from exchage 2003 on new BES5.0.2.
-If it works remove that user and do the same but activate (not migrate yet) one user whose mailbox is on 2010 on BES 5.0.
-If both works try migrating user from BES 4.1 (with mailbox still on 2003 exchange) to a new BES 5.0. Make sure it works.
-Then move mailbox of that user to a new exchange 2010 and see if that works too.
Good luck.