The main things to look at would be:
1. Check that you have created the Inbound Mail and Outbound Mail services in Configuration Centre.
2. Check the services are started.
3. Check the server's event log for any errors being reported by either service.
Then as DMS said check the Mail Manager section of Community on how to troubleshoot anything logged.
Thanks guys for all the replies and sorry for getting back to you so late. Basically we made it worked on Exchange 2010 after upgrading to ServiceDesk 7.6.2.