From Jay Hilyard and Stephen Teilhet (C# Cookbook): “Every time you set the Query property, the UriBuilder class appends a ? to the front of the query string information.” This move should solve the problem:

Uri u = new Uri("http://contoso.com/mypage.html?foo=0");

string uriString = u.AbsoluteUri.Replace(u.Query, string.Empty);
string queryString = u.Query.Contains("?") ?
    string.Concat(u.Query.Replace("?",string.Empty), "&", "foo=1") : "foo=1";

UriBuilder builder = new UriBuilder(uriString);
builder.Query = queryString;

Now Jay Hilyard and Stephen Teilhet recommends using a .NET 3.5 extension method pattern to permanently fix the problem:

public class UriBuilderFix : UriBuilder
{
    public UriBuilderFix() : base()
    {
    }

    public new string Query
    {
        get
        {
            return base.Query;
        }
        set
        {
            if (!string.IsNullOrEmpty(value))
            {
                if (value[0] == '?')
                    // trim off the leading ? as the underlying 
                    // UriBuilder class will add one to the 
                    // querystring.  Also prepend ; for additional items
                    base.Query = value.Substring(1);
                else
                    base.Query = value;
            }
            else
                base.Query = string.Empty;
        }
    }
}