Thanks Fletch, Figured it out.
I set up users as All converged users, but I didn't actually go in and update the users in the converged setting, you have to add:
00001(nxx)(extension)
then below it
nxx+extension@domain.com
So it should have looked like:
000015551111
5551111@mydomain.com Enterprise Converged Setting
I added that and made sure of the above and it works like a charm now.
Thanks