Anche se non hai spiegato benissimo, credo di aver capito che certi ambienti (ad esempio, di per certo JavaScript) "escapano" lo spazio con + invece che con %20.

Usa il metodo replace(char, char) della classe String prima di farne il decode.