Fixed the problem myself, for reference for future people who may have this issue:
The issue is, Spelunky sees my gamepad as controller #2, so it doesn't let me bind to it.
How to fix this in Windows 7:
Start Menu > Devices and Printers
Then select the game controller you want to use (Xbox 360 Controller for Windows in my case), right-click and select "Game Controller Settings". A dialogue should pop up with all your game controllers listed. In my case, it was seeing my Logitech G13 as a game controller as well as a keyboard.
Press the "Advanced..." button, and a dropdown window will appear letting you "Select the device you want to use with older programs." Pick the controller you want, this one will now be "Joy1".
That's it, now you can bind your controller and be happy.

Hopefully this helps someone sometime.