They still connected as a media device. The volume control on the computer still worked. But no sound at all would transfer between my computer and the headphones. Weird.
First Things First
Let's make sure they're configured in the first place. Consult your manual on how to sync your device. Then, from your desktop environment's settings (if you're not using a Desktop Environment, check out blueman), click "Bluetooth"
It should say "Connected". This is a sign that the bluetooth device is properly connecting to your Linux box, but not that audio is properly being transmitted.
A Lesson in Linux Audio
Linux Audio is notirously painful to configure. There are 3 sound systems that distributions tend to use. These are Alsa, PulseAudio, and OSS, which really isn't used all that much.
How To fix
Okay, so now you have to install a package called pavucontrol, which is short for Pulse Audio Volume Control. It's not installed by default on most Linux distributions because it provides some more advances facilities for managing your audio. Once it's installed, run "pavucontrol" from a terminal to open it.
First, make sure that the audio isn't muted on your headset here (either on the bar or the speaker mute button). You should have your channels locked together, and it should be a fallback. Now, if all of this is set up (it was for me), there is one last step you need to do to fix your audio.
In the "configuration" tab at the top, go down to your headset. As misleading as it is, change your headset from either "Off" or "Headset head unit" to "High Fidelity Playback (A2DP Sink)"
Now, after changing that, you should be good to go. If you're not, there is one last thing you can try.
Install alsamixer if you don't already have it and run it in a terminal. If you see "MM" at the bottom, hit "M" to unmute that channel, and use the up arrow to turn the volume of it all the way to 100%. If it's possibly reading your sound card wrong, you can use "F6" here to change that.
Good luck. Audio issues are a true pain to work through, and are seemingly impossible to fix. Hopefully these steps solve your audio problems as they did mine.