Ok...VERY confusing for the 'lay' person. 
I revoked ALL access here: https://accounts.google.com/IssuedAuthSubTokens

Rebooted the phone (removing battery again)
Generated an Application-specific passwords and named it Atrix
When prompted entered that p/w into my phone.

Deleted ALL apps that synced with gmail and reinstalled them

Phone seems to be working properly now.

This works for the person who PANICS when their email still works after changing it online, however for the regular Joe who wouldn't think that it need to be changed on their device it won't. Google needs to address this asap!!