If you're still under warranty Canon will replace the grip for free. They did mine, and the turnaround was less than a week. I'm almost certain that the newer rubber grip is smaller and fits way better, and is a touch firmer, but still very grippy. The original rubber was very soft and squishy which I'm sure contributed to it coming loose.
Even if your camera isn't still under warranty I'd bet that the repair woudn't be very pricy through Canon.
If you decide to have a go at it yourself, I've seen repair kits on eBay to re-glue or replace the rubber grip.