Вот я делаю HttpUrlConnection без дополнительных хэдеров, отправляю запрос на сервер. Потом делаю новый и добавляю Authorization хэдер. А сервер (поинт) говорит, not authorzied. А если перезапущу приложение и сразу второй запрос с тем же хэдером - уже все ок.