I noticed a while ago that my Google apps for your domain email wasn't pushed to the Blackberry at once. There was some debate on different forums on how to solve this, with the most credible one being to call AT&T, escalate to RIM and get them to mark your domain as a Google Domain.
However, the solution is simpler, just make sure that the highest priority MX is ASPMX.L.GOOGLE.com. and BIS will do the right thing. (At least for AT&T BIS).
(Usual reasons for this not being the case is if your domain is being filtered through something else.)