I'm answering my own question, so that it may help others who face the same issue.
This particular issue arises when you make the following import in the current workspace before executing anything else.
from __future__ import unicode_literals
This has somehow turned out to be incompatible with the following sequence of code.
from urllib import quote_plus
name = u'Mayte_Martín'
quote_plus(name.encode('utf-8'), safe=':/')
The same code without importing unicode_literals works fine.