Have you edited the default HTML for the email that goes out? If, perhaps, it had an error in it, it could be hosing up the mail routine.
Is the administrator or whoever getting the order emails? Is it just the email going out to the shopper, or is it both emails (the one to the shopper, and the one to the store manager or whoever gets the orders)?
Have you tried placing an order yourself, with a local email address? Does that email go through? If it does, then there's nothing wrong with the mail routine in the cart, but instead something with configuration of your mailhost or delivery system.
I guess what I'm saying is that you've got to be methodical about it. The fact that you can send a newsletter indicates that DNN is configured properly for SMTP. Now, we need to figure out what's not working properly.
I'd be glad to help you work through this, if you like.