I used a circuit like described in the link above. 10k ohms pull down resistor and a big switch.
There's more wire than I need between the arduino and the switch, I'm going to trim it, hopefully that will also help.
I'm getting button presses without hitting the button at all. The second occurrence was at least two minutes from the last real button press.