Generate your proxy (Say, "TestProxy") then do:
TestProxy.YourServiceClient client = new TestProxy.YourServiceClient();
Dictionary<string, string> testDict = new Dictionary<string, string>();
testDict.Add("test", "test1");
client.SendData(testDict);
WCF will serialize your Dictionary with no problem. The problem here is that you are trying to access your WCF service as if you exposed it as a REST Service through an HTTP Get request. I'm pretty sure based on your question, you aren't exposing this as a REST service. If you want to be able to do Get Requests, then google .Net WCF REST.
*Note: you might also want to look into the Request/Response SOA pattern, it's going to save a bunch of trouble down the road.
Update:
Here are some links that might point you in the right direction, you'll probably want to expose your WCF service as a JSON endpoint.
JSON / REST Link
Search Dictionary in this LINK to get some details on alternatives and gotchas in WCF JSON.
Hope these help. I have never done an Iphone app so I don't have any source code to give you.