Bit of an over exaggeration of having to redo the entire theme, most things can be accomplished with CSS alone and if you are not fussy about having every single function that the full site offers responsiveness is more than accomplish-able with CSS and a couple of template tweaks.
Ive been working on on for
http://www.tottenhamhotspurs.tv/forum/ , its not completely finished yet but its usable as a responsive theme.
I do agree with Zach though with price ranges, depending on the theme being done it could be anywhere between $1000 - $3000.