If you can get the bit out, try using an impact gun, or at least a hammer to get the bolt to break free. If you use an impact gun, just make sure the bits are rated for that, or you'll end up in the same place again.
Like Justin said, use heat....even when trying to get the broken piece out. Use a chisel and hit the broken piece clockwise to free it up. If all else fails drill her out using a high quality hardened bit.