Hi all,
I've lived in Columbus for over 10 years, and I think it's such a great city. I haven't read the whole thread, but in case this hasn't been posted yet, http://www.metro-rentals.com/ is a great place to search for apartments. I once had a 1br in VV for $350, but it was seriously tiny. I would expect to pay more like $500-$650. I recently lived in a 1BR in Grandview for $550. My girlfriend also had a 1BR in Clintonville for $400. I agree with the suggestion that Olde Town East is a little more removed from campus, but you also get more bang for your buck there.
My favorite apartment in Columbus was through Kohr Royer Griffith - http://www.krg1.com/ They seem to really take care of their properties. I once looked at one owned by http://www.myersrealty.com/, and it wasn't taken care of at all. Maybe that apartment was the exception, but especially for those of you trying to rent from out of town, I would be cautious with them.
ETA: You can find deals on mentro-rentals, but that site seems to skew a bit on the expensive side. Don't let it make you think every 1BR in Victorian Village is $1,000/month.