We had the same problem as originally posted, where 2 and 3 worked, but not #1:
1 ) Generic Java client based Code ( See the code below)
2) WM API ( client.jar) based Code
3) Browser
We were already using basic encoding, but still failing. Thanks to the post by Rupinder Singh about using base64 encoding, it works. So thanks!