Hi,
If the email notification can be sent when you change the status of the order in the backend, then it should indeed also work for when the order is created.
If you have the Business edition or HikaShop 3, make sure that the emails are enabled in the menu System>Emails.
Because if you disable the emails, they won't be sent.
Also, check that the settings of the emails are correct there.
Finally, you can also check in the menu Customers>Emails history.
If you see the emails there, it means that HikaShop successfully generated them and sent them to the email server.
And thus, the problem is to be looked for in the email server log with the information of the email there.
If you don't see the emails there, it means that HikaShop didn't generated them. It could be a crash of the processing during the email generation (for example if you customized the emails in a wrong way). It could be that the emails are disabled. Or that their settings are wrong in some way.