Also, sounds (unsurprisingly) like we're reinventing the wheel. Python may not be a web framework, but Django is, and provides better tools for this:

http://stackoverflow.com/questions/5036498/django-rebuild-a-query-string-without-one-of-the-variables
http://stackoverflow.com/questions/5755150/altering-one-query-parameter-in-a-url-django
https://docs.djangoproject.com/en/dev/ref/request-response/#querydict-objects

Something like

    from django.http import QueryDict

    (scheme, netloc, path, params, query, fragment) = urlparse(url)

    query = QueryDict(query, mutable=True)
    query['short_redirect'] = redirect_param
    return urlparse.urlunparse((
        scheme, netloc, path, params,
        query.urlencode(),
        fragment
    ))