Hmmm, just checked www.eqtraders.com to make sure, and indeed 1 sharpening stone + 1 rusty weapon should yield 1 tarnished weapon on success (and I think it eats the stone and returns the rusty weapon on failure, unless my memory is cheated by some spell).
At the risk of insulting your intelligence, double-check that you are indeed using a forge and not another static tradeskill container like an oven or kiln. The oven and the kiln look somewhat similar to the forge so you might just be at the wrong one. If I had a silver piece for everytime I used the wrong one because I wasn't paying terribly close attention...
The only other thing I can think of is to double-check that you are indeed trying to combine a rusty weapon and a sharpening stone. The icons for these items certainly aren't unique. It could be that you are trying to sharpen a tarnished (i.e. already sharpened) weapon, or that you are trying to sharpen your rusty sword with a rujarkian potato or something like that.
Also make sure that you aren't trying to combine a rusty weapon with a stack of sharpening stones. It only works (for now) with one of each.
Other than that, I don't know of any other reasons why this shouldn't work. Good luck!