Okay, I figured it out, should have realized it earlier: the problem is that I have Synergy running, and was trying to control the client computer with the shortcuts. Everything else works (the shortcuts on the server computer, the non-itunes hotkeys on the client computer, and the keyboard shortcuts in the itunes app itself).
Was able to just add a hotkey workflow as a workaround (Templates -> iTunes -> Next track from hotkey)