For Restless Leg Syndrome I've always heard to add B Vitamins.  This little 
article says to add Magnesium too:

The most common reason for Restless Leg Syndrome is a magnesium deficiency and 
Vitamin B deficiency. A magnesium deficiency will cause muscle tightening in 
the legs with spasms. A Vitamin B deficiency may cause the neurological problem 
and cause the "crawling creeping feeling on the legs". But what about Restless 
Leg Syndrome ( RLS ) causes these two deficiencies? According to John Lee, MD, 
Estrogen Dominance causes Magnesium Deficiency and Vitamin B deficiency. 

>From People's Pharmacy:

This home remedy mystifies us, but we have heard from many readers like you. 
The risk of unwrapping a fresh bar of soap and putting it under the bottom 
sheet where the legs will be is almost zero. The cost is far less than a 
prescription. Positive responses from other readers experimenting with Ivory 
soap remedy: 
"A while back I wrote to complain that the bar of soap under the bottom sheet 
quit working for my restless legs. (It was great at first.) Then I got to 
thinking, it worked before, so why not now? That bar of soap had been there for 
six months, so I replaced it. The result: no more restless legs. A few times 
that I had symptoms, I put my feet on the soap and the sensations went away in 
about two minutes. 

"My husband was having severe leg cramps at night. Without telling him, I 
placed a soap bar under his sheets for two nights before he noticed. It worked! 
He's had no more cramps. We still can't believe it! "

"I have had severe leg cramps for years. When I read about putting a bar of 
soap in bed, I got a bar of Ivory and put it under the bottom sheet near my 
legs. It's been a month since I did that, and I have not had one leg cramp.  
http://www.peoplespharmacy.com/archives/home_remedies/index.php?page=all

Cindy