The solution that worked for me was to Backup and then Restore.
For the backup: you can do it via iTunes (plug the iPhone and right click over its icon on the Devices section and then choose Back Up) or download your photos, contacts and other important documents to your Mac using iPhoto (just download your photos) or apps like My Contacts Back Up (it will email you the full list so you can upload it to the iPhone later). Make sure you backup properly please!
After you have done the back up choose Restore in iTunes and that will erase all the files and apps from the iPhone so it will be back to the settings it had on the day you used it for the first time (you'll be able to recover all the apps you paid for since they'll be linked to the Apple ID you used to purchase them).
The iPhone will still have the latest version of iOS (6.1.3) so if the problem is -like in most cases- software related it would be fixed and you'll able to pair the device again. If not maybe you will have to downgrade the iOS to the previous version.
Hope this helps!