Luckily you're on gmail (for no other reason than gmail and Google Apps being better than everything else). I would do this:
1. Change your password
2. Set up 2 factor authentication.
3. If you use a mail client, update it and every other part of your OS to the latest and greatest version. If you're using a version of Windows you got from BitTorrent, understand that you're likely entirely compromised. Reinstall a legitimate OS and build up the system from scratch - preferably Ubuntu 13.04 presuming you're not on a Mac.
4. Create application-specific passwords for your different devices and mail clients.
5. Email everybody and apologize for the intrusion. This is a great time to tell them what you're up to and reconnect with a long-lost friend and maybe ask about career opportunities. I have a friend who kindled a relationship with his now wife after reconnecting from a hacked email account.
Hope it works,
Adam