Ans:URLに日本語文字列が入ってるとエラー

urllib.quote_plus(url.encode('utf-8'),':;/')

が正解でした。ただし'utf-8'なのは相手がutf-8で処理してるからなのだけど。

これで

http://s3.amazonaws.com/twitter_production/profile_images/82135063/名称未設定_1_のコピー_normal.jpg

が

http://s3.amazonaws.com/twitter_production/profile_images/82135063/%E5%90%8D%E7%A7%B0%E6%9C%AA%E8%A8%AD%E5%AE%9A_1_%E3%81%AE%E3%82%B3%E3%83%94%E3%83%BC_normal.jpg

となった。