mrkrag, the phone should be able to see your mail for a short while (probably a matter of minutes), but the first time your phone tries to sync (your refresh your inbox, you send or receive new email, your phone does it's regular backgroud sync, etc.) you should be prompted to change your password on the phone.
If your phone's already done some of those actions, does your phone still send and receive mail correctly? And could you tell me the model of phone you're using? And the version of the Gmail app (Settings > Applications > Manage applications > All > Gmail)?