If you are using the stock recovery, you can give it a try withUnlockRoot.com
If you aren't using stock recovery and you want to root it via recovery, than here is a [URL="http://forum.xda-developers.com/showthread.php?t=1467128"]HowTo[URL]
Don't download a firmware. Scroll down to Others and choose the stock recovery and flash it via ODIN.
Than apply the root update.zip via stock recovery.
I would like to find out, what causes this issue. For me rooting via recovery worked without a problem.