Going the cobbler route sounds like the best idea, as long as the guy has been doing it for a while. You obviously want a good job done on these, not a half assed job. Ask first, see if they even can fix em up.
You're right about REI, though, they don't stock shit, but you gotta love the return policy. Good luck on getting them fixed. Post again if you get em done, let us all know how it turned out.