Rear tail lights do not work. Went out. What to do?

Are you absolutely positive you have a good ground??

It does not sound like you do seeing as the only thing you have done is to remove the bulbs. The power feed for turn/brake and tail are two seperate circuits, so the only common denominator is a bad ground.
The bulbs are in the right way?