I've searched extensively for this exact problem and can't find the solution to this problem.

Site built on Version 1.5.5.1
Email doesn't work, but only when a new order is placed (contact page and new user signups DO generate email)
I added a secondary email (additional email alerts) and this doesn't receive an order notification either
this is a clean build (not an upgrade),
Any hints/tips would be greatly appreciated to resolving this.