I was having problems with the old redoable theme on WP 2.5 so I went looking for something that'll work and wasn't too difficult to tweak.
This one is called RedLine and it is produced by Blog Oh Blog. So far I don't see any bugs with WP 2.5 and everything went smoothly. I even added a plugin to handle google searches locally and shoe-horned in my ads. A couple other problems are also fixed, most notably the tag and category pages now work properly.