Не приходит уведомление о новом заказе на почту

А почта вообще работает? Сообщения формы обратной связи, например.
Попробуйте проверить, работает ли функция mail в командной строе php:

var_dump( mail( "ваш@адрес.ру", "test", "test" ) );

true - значит сообщение отправлено.
false - не отправлено. Ковыряйтесь с настройками сервера.

Кстати. Ваши уведомления о заказе никуда не потерялись. Их можно попробовать отправить повторно с помощью модуля «Управление почтой»
http://marketplace.1c-bitrix.ru/solutions/askaron.mailmanager/

Тогда надо разбираться с почтовыми событиями. Есть ли почтовое событие о новом заказе. Какой статус отправки почтового события.

Попробуйте сделать запрос в таблицу b_event, если ваши события там созданы то проблема может быть в том, что выставлены костанты BX_CRONTAB и BX_CRONTAB_SUPPORT в файле /bitrix/php_interface/dbconn.php. Найдете их там ставьте в false.