Since gold hasn't really played a roll in diablo before (tho it might in the next game) the only real thing i can see for respec cost would be maybe sacrificing powerful runes (the higher the level the more powerful ruins to be sacrificed) or possibly losing levels for respecing. Maybe some type of rare tomb that has a one time use or i suppose sacrificing gear for it.
Gold hasn't been used before because you haven't been able to do anything with it. I'll make a forumal right now to show how it could be done.
Clvl*b*n=Cost of respec
B = Number of skill points respeced
N = difficulty. Say, 1000 for normal, 2000 for NM, and 3000 for Hell
So, say a level 15 barb is going to respec his first 3 skill points, on normal.
Obviously, it would need work. But you should understand that this service would give gold a real value.
This seems ok.. but I think it could still be a bit more expensive. (the money value in d3 could be different tho but if we think with d2 gold amounths) People would trade items for gold in order to get a respec.
Also I think that gold should be used to buy a magical item from vendor that can wipe your memory and teach new things. So it wouldn't just be some trainer that resets them, would be more realistic
nzkobc has definatly got it right. With a point based respec system with heavy cost you can undo bad skill choices or get rid of a skill that you just don't like without seeing everyone respeccing to the "flavor of the week".