Are you sure you read 2-4 uF? Or is that 0.2-0.4uF? It would make sense if you are soldering them to the board and they are in parallel (4x caps at 100nF --> 0.4uF).
I would be very surprised if you have bad capacitors. Either think about the above, or maybe let them cool down a bit? I don't think getting them too hot would cause a huge capacitance, just the opposite.
If you're going to go the Digi-Key route I'd say the 'good ones' are C0G/NP0/X5R/X7R rated (not the crappy Y5V or Z5U types). Beyond that...get the cheapest ones
: compatible with Arduino UNO, 24V operation, all I/O's fused and protected