Change encoding to use `%20` for spaces

A couple of bugs have cropped up recently in which queries with spaces in
arguments would receive a `403` status from services when they were otherwise
well-formed requests.

It appears the Java services have changed from expecting spaces encoded as `+`
to expecting `%20`. At first I thought this must be a long-lived bug in the
`Authenticate` class, but when I checked I noticed we have
_always_ sent spaces as `+` going back to May 2012. Indeed the specs
themselves tested for this case.

cr: @krobi64, @shunchu, @jzhang-bk