On my Mac I have not upgraded to Lion. I'll do that tonight.
But between the phone and iCloud I may figured out what was wrong. I didn't have iCloud as my default email account. I changed that just before lunch and tried once I got back. 30 second delay from email to the alert on my phone. Didn't show my email message on the lockscreen though.... 😕 Looking into that now.