Ok people. I've tried all the fixes suggested by you folks here. None worked. I contacted Apple care and they emailed me the following :
First, try the SMC and PRAM Resets:
SMC Reset (Macbook/Macbook Pro/Macbook Air):
1. Shutdown the Mac.
2. Connect the MagSafe Power Adapter (Charger).
3. Observe if the MagSafe Power Adapter (Charger) light is Orange or Green.
4. Locate the Shift, Control, Option, and Power keys.
5. Press and Release the Shift, Control, Option and Power keys on your computer. The Mac will not start up.
6. If your MagSafe Power Adapter Light (Charger) was Orange, you will see it turn Green, then back to Orange. If it was Green, you will see no change.
Then, PRAM Reset
1. Shutdown the Mac.
2. Locate the Command, Option, Letter P and Letter R keys on your keyboard.
3. Turn on the Mac, and immediately hold down all four keys at the same time.
4. You will hear the initial chime. Continue to hold the keys until you hear the chime a second time.
5. Let go of the keys when the second chime plays, and let the Mac start normally.
If the issue persists, try a test user account:
To do the Test User:
1. Go to System Preferences by clicking the Apple Menu.
2. Go to Users and Groups (Accounts in OS X Snow Leopard).
3. Click on the lock at the bottom of the window.
4. Click the at the bottom of the white box.
5. Set the account type to administrator, and set all of the settings to "test". This includes the full name, account name, password, etc...
6. Click the lock to lock the preference pane.
7. Click the Apple, then "Log Out ..." and log out.
8. Click the test user, and sign in. You can skip any setup at this time
9. Try to test out the bluetooth audio connection and see if the issue persists here.
I tried this out a couple of times (not the test user thing) and the issue was resolved.
Cheers!