I was in Lençois in 2006.
Leicos from Parnaiba - only by car and there was a direct path. I had to go through a town called Chapadinha. Look on google maps.
Atins, Caburé or Barrerinhas? I was in Barrerinhas (http://www.pousadamurici.com.br/index.html
). It has several hotels and places to eat. This site has several boats that take you to the peaks.
Atins is far and had no infrastructure.
Caburé at the time had no hostel, but had restaurant (Caburé Restaurant very good). The wind is constant and the beauty of the place is indescribable. Wind above 20 knots.
I hope I helped,