Extremely easy fix, no third party apps necessary.
Google Chrome hijacks the media keys if you have Google Music Chrome app installed (and I think it's installed by default). Just go to "chrome://apps", right click on the Google Music app and click uninstall. It took me two seconds and the media keys immediately worked for Spotify. No need to reboot or nothin.