Yes, I’d say the switch is bad.
I was just thinking, you said, there were four wires coming out of the switch, I wonder if it’s possible that you just swapped two of them. Doing that would cause exactly this problem. If the switch has four terminals, you need one set of wires to go to the bottom ones and one set to go to the top ones. If the screws are different colors (brass on one side, silver on the other) hook the colored wires up to the brass and the white wires to the silver.
Are both the white wires on the same side? Are their corresponing colored wires also in the right place (if one white wire is at the top, the colored wire that comes into the box with it, should also be at the top).
Does it say ON/OFF on the switch itself? I’m still wondering if you got a three or four way switch by accident.
I’d love to help your troubleshoot this problem, but at this point, I think it’s going to involve the use of some testing equipment (voltage detector at the least) and some pictures with labeled wires.
If you want to try something, try this:
Take the switch out, twist and cap the white wires together, twist and cap the colored wires. Turn the breaker back on (it was off, right). Fan comes on? Good.
Now, turn off power, separate the colored wires, turn power on. No fan? Good.
Now, go out and buy a switch, it should have to screws plus a ground screw. Attach your ground (copper or green wire to green screw), attach one colored wire to each screw, reinstall switch into box, turn power on, test switch. Works? Good.
Honestly, at this point, I think the first switch was bad. The new switch, switches both the hot and neutral lines (like the old one) and maybe you wired it wrong, maybe it had a different configuration and even though the wiring looked the same, you just bypasses the switch. Who knows.
