Now I feel stupid,
Why? No one is born with a knowledge of "floating pins".
Enabling the internal pullups on pins 2 and 3 (set to input) just gave them a permanently HIGH input reading, even when the switches are not closed.
Did you change the switch to ground the pin when closed? For pull-up resistors, the switch is connected to GND. For pull-down resistors, the switch is connected to VCC.
Edit2: Touching the 1k resistor while it is connected to ground seems to fix it. I'll try with a 10k.
Your circuit is not correct. You still have a "floating pin".
Does this help...http://www.arduino.cc/en/Tutorial/button