In a recent Nightwalkers issue (I think, but I can't find it online), there was a suggestion that you get tested for ferritin in addition to a standard iron test. I talked to my doctor about this and he prescribed the test, although he was skeptical, saying my family history of RLS indicated that the problem was more than just iron/ferritin.
The test showed that my iron levels were OK, but my ferritin was slightly low. He prescribed iron supplementation, and my RLS has all but disappeared. (It took a few days to see the results.)
I know that just because it works for me, it may not work for everyone. But I urge you to get tested for ferritin, just in case. It's definitely worth a try. And the standard disclaimer -- don't just start taking massive iron supplements without getting tested; it can be dangerous!