Are you positive you have 'New Ticket:' alerts enabled?
Does that department have Autoresponders enabled?
Admin Panel >> Departments >> Department Name >> Autoresponders. Select enable "New Message".
What are some server stats? MySQL version, PHP Version, etc...