all other light switches and outlets work.. in the bathroom and every room on the 2nd floor!

Could the issue be with the ceiling light, causing no power to get down to the switch? Grasping for straws, here... maybe replacement switch is bad too?

Forgot to add above that there are little indicator lights on the side of the switches, none of them are lit.

Depending on how old your house is, the GFCI that controls that circuit could be almost anywhere. I had a house where the bathroom circuit was controlled by a GFCI in the garage. At one point in time the code was much more lenient with GFCI usage and the devices were expensive.

Have you reset the breaker for the bathroom? Turn it fully off and then back on. Sometimes when breakers trip, they don't always give an obvious visual indication.

Hi mike. Yes, at one point I had most of the power off upstairs. I changed a ceiling fan in another bedroom after I changed the switch and because the breaker box isn't labeled clearly, I tend to go crazy turning things off.

I will turn off and on every single breaker to see if that does the trick. After reading what you said, I remembered that there is a weird breaker that controls an outlet in the kids' bathroom -and- an exterior outlet right outside the front door and I think the garage. Crazy, goofy house!