Have you check contact resistance of the switch when it is pressed? What kind of contact surfaces the switch has?

With too strong pull-ups you might get this kind of problems if switch is unreliable (leave on some high ohmic state even when pressed).

BR,
-Gusse-