Even a pretty fast motor, like 10,000 rpm, would only do about 170 connections per second, which should be perfectly possible to track with an Arduino. Is it perhaps the case that your aluminum foil causes contact "bounce"?
That being said, reading the speed of a motor is a very common problem, and is typically done with either quadrature (relative) encoders, or absolute encoders, either optical or magnetic. You can buy encoders that you attach to your motor shaft or gearbox, and that will give you clean pulses to measure.
If you must build your own, I think a phototransistor and LED and a comparator or opamp will work pretty well. You should install a pin-change interrupt on the pin that the count signal comes in on, and have the interrupt routine count the number of ones or zeros.