All indexed Shimano rear derailleurs and rear shifters (except pre-9-speed Dura Ace) use the same cable pull ratio; so they are compatible. (It's the front derailleurs that are not perfectly compatible.)

You're on the right track, get any Shimano MTB rear derailleur rated for at least a 32T max cog size (which is the vast majority).

Another thing: if you want to keep the same orientation for the rear shifter (i.e., brake lever for down-shift, thumb lever for up-shift), then get a Rapidfire (traditional, high-normal) model vs a Rapid Rise (low-normal) rear der.

Lastly, you should have got a new 8-speed chain when you changed out cassettes (or added extra links if the chain was new enough). Size the chain like this: http://sheldonbrown.com/derailer-adjustment.html#chain .