Вы кодируете всю строку запроса, а не только их значения .Вы должны сделать что-то вроде
var values = new Dictionary<string, string>();
values.Add("firstname", "Joe");
values.Add("lastname", "Average");
var querystring = String.Join("&", values.Select(pair =>
pair.Key + "=" + HttpUtility.UrlEncode(pair.Value)).ToArray());