What I am suggesting needs to be done every time you try to connect the Bluetooth device so it's a bit annoying. I use Bluetooth headphones so I have to do the following steps:
Connect the Bluetooth device (Wi-Fi won't work now).
Run this command:
sudo service network-manager restart && sudo service bluetooth restart
If Wi-Fi and Bluetooth still don't work simultaneously, do the following steps:
Turn off Wi-Fi.
Turn off Bluetooth.
Run the command:
sudo service network-manager restart && sudo service bluetooth restart
Turn on Wi-Fi.
Turn on Bluetooth.
The above steps work for me. Do post a better solution if you find one.