Hi madcow,
You have a few options if you have a couple years to spare. You pretty much listed them, but I'll pick out the ones that are more useful:
1. You DEFINITELY want to get a 740+ GMAT Score. I picked 740 out of my pocket for no apparent reason, but you need something ABOVE the mean and median of the top 10 schools. You want both your scores to be above the 80% so you can write your optional essay saying, "See? I am smart enough in math and verbal to handle the rigors of B-school. You can ignore my grades."
Hitting 800 is actually a curse sometimes (we had some discussion about this somewhere) because some top 10 schools (Stanford) loves to reject all the 800 applicants.
2. Take classes in which you had your bad grades in, and ace the class. So if you got all your bad grades in math, take some math classes at extensions or community colleges and get an A or A+ in them. Same with other subjects. A masters program might work, as long as it's rigorous in coursework (engineering, science, technical, finance, etc...) if you get a 3.5+ GPA in that degree.
3. Definitely apply to some 2nd tier schools as "safety", because you NEVER know what the top schools will do. It's a random process, even for the 800 GMAT and 4.0 person. If you have any weaknesses in your app, it becomes even more random. I would apply to at least 1 2nd tier school... But keep it in the Elite/Trans-Elite/Near Elite arena.
In the end, you want to address specifically what your weak in and what caused your GPA. If it's math and sciences, then take those classes and get good grades to compensate. If it's english, do the same for english. People with low GPAs have gotten in, but with some hard work and compensating with classes or GMAT. Pelihu had a 2.x GPA, but had a 780 GMAT and some great experiences he can talk about. I believe Nervous showed that she can do quant with extra classes. The stories go on and on.
The application is a process that looks at all your qualities, so make sure that your GPA is the ONLY weakness, and also try to compensate for it by the methods above.
Good luck and hope that helped!