Ok, I went thru all the listings that RadioShack has for relays, I didn't see any that were 5 or 6V for the coil & 58ohm resistance.
Is it this one?http://www.radioshack.com/product/index.jsp?productId=2062480#
However, with 6v & 58 ohm you described, your transistor needs to sink ~ 100mA.
The 2n2222 is certainly good for that if you are turning it on enough.
With 5V coming out of the arduino and a 180 ohm resister, that should be putting around 24mA into the transistor, and with its gain of 50 that should certatinly be enough to be turned on full & drive your relay.
What is your code trying to make it do?
Use the # sign above & paste in your sketch between code & /code.
Maybe you just need to slow down how fast you are turning the relay off & on.