Actually, on rereading your original post, I think I had misread it. From your description of what happened when you changed out the switch, I originally thought that changing the switch didn't fix the problem. On rereading, I now assume that when you said that with the new switch you got "nothing" that means that it didn't work at all with the new switch (vs. running all the time).
If that's the case, (and assuming it wasn't something simple like the breaker being left off) I'd recommend just going into the outlet box (with the breaker off) and making sure all connections are secure and no sign of any obvious problems (like burnt insulation, etc.). My guess is that one of the black wires is loose there, and may have initially had wires shorted together, later possibly getting pulled apart (forming an open circuit) probably while pulling on the wires while replacing the switch.