Ok, I didn't think about it that way. So really this is as much a floating input issue as it is a button debouncing problem, because the bounce is returning down to the power board causing noise. That makes a lot more sense now. I'll add resistors to the gate pins on each of my buttons and hopefully that will get it to work.
So I implemented this solution with 10k resistors and I'm still having the same problem. To try to isolate the problem I made a breadboard circuit using similar buttons in the manner you described. Here is a picture of it.
Yes you have improperly followed my instructions (trice times!).
It's hard to be sure from the picture, but it looks to me as if you have the resistors wired in series in the line between the switch and the Arduino input. That is not the correct way to wire up pull-up (or pull-down) resistors.