The obvious question would be "when you put your deck back in were all of the cables put back in SECURELY?"
If the answer is yes then I suspect a blown fuse in your amp. I'm not sure if the sub operates off of a seperate amp from the rest of the speakers, but given the nature of a sub amp vs a speaker amp, it's pretty common to see them seperated.
If all you did was remove the head unit then it pretty much has to be one of those two things.
Blown speakers don't just stop playing, they just sound like crap. Blown amps stop playing, but 19 times out of 20 amps will blow their fuse/breaker before they'll actually blow up from an overload.
I have a giant (around 100 pounds, 700 watts x 2 channels RMS, up to 1200 RMS x 2 channels at its 2 ohm min... and they don't even rate peak power because that'd just be pointless) high-end 2-channel amp in my house that is used to power a whole-house audio system (up to 8 pairs of speakers simultanously in all different locations around the house).
Anyway... point being that the amp has seen some SERIOUS feedback and over-voltages in its life time. It doesn't use a fuse, it just uses a breaker. So you switch the power off, and back on, and it's fine. Better amps will do this, but any amp is at least going to have a replacable fuse that accomplishes the same thing.
