How close to ground is close enough for a relay?
First, the voltage from collector to emitter for a BJT will be about 0.2V minimum in saturation mode.  Your DMM was making an inaccurate reading for some reason.  This limit can be overcome by using a MOSFET, which will simply provide a tiny resistance (5ohms to 10s of milliohms) and, consequently, a tiny voltage drop. 

You didn't post any information about your relay, either.  Are you operating it within the specified voltages?  Some relays will work at 5V, and some will not.  Whether it's referenced to ground or not is gloriously irrelevant - Just provide it with the datasheet specified voltage/current, and don't worry about your ground.

All that being said, however, I would guess that you've simply blown up your transistor.  The coil in the relay has a lot of inductance and a lot of current, and switching it can generate damaging voltage spikes.  If you're using a 5V relay, just hook a 5.1V zener across the coil (cathode to 5V, anode to the collector of your transistor).  This should help protect your electronics.  With the zener in place, give it another try.  (Note that there are more sophisticated protection methods if you need it, but I've always found a zener sufficient for reasonably rugged transistors with the small signal relays I work with - How big is the relay?).