There are a few likely causes here which we can go through systematically:

1) Did the email go out after a delay? 

2) Can you test the emailing system by setting up a dummy program and using the messaging functionality to message a test user? 

3) Can you check for a 'nomail' statement in the config file?

4) Has the messaging system been disabled under Site admin>advanced settings?

5) Is it a problem with the email server?

cheers,

George.