Em vez de formatar, tente remover a partição e, em seguida, adicione uma nova e, em seguida, formate a unidade. O Editor de Partições do Gnome é uma ótima ferramenta para isso. Ele pode fazer praticamente qualquer partição e sistema de arquivos relacionado.
Se ainda não for possível, o stick provavelmente está com defeito. A mídia flash se desgasta com o tempo.