I recently replaced a 3-way switch and the replacement looked identical to what I took out. However, after reviewing the spec sheet, I realized that the manufacturer had switched the terminals around. I know you say that the hot wire is on the proper terminal, but is that based on wiring it up with the wires in the same positions, or on having absolutely verified what all of the terminals are? Don't mean to be insulting...just throwing out a possibility.

My lack of electrical understanding is so low, insult is impossible :)

I did verify the hot and connected it to the dark colored terminal that has no screw opposite it. Thinking more about it, I figured the only other reasonable possibility is that the hot was still on the wrong terminal, so I swapped the blacks and now all is good.

Congrats!