Hi,
I had similar issues with my workflow... so, I put a log in the workflow, so I could see what was happening. You can do this for any step of yout workflow.
If you check the workflow in Sharepoint, what does it say when it tried to send the email?
To resolve our problem, we set a 'Pause for duration' of 1 minute before the e-mail was generated. For some reason, it wouldn't send immeadiately (if at all)... however, after a pause it seem to send without fail.
Maybe it will work for you.
Jay