I, too, had a hard time using my Bank of America/Visa card in Brazil. The only place I was able get cash was at the Banco 24 Horas but, as someone already mentioned, you can get only R$100 after 9 pm. This was created as a security measure since many people were taken at gunpoint to the nearest ATM and had to withdraw all their money just to give it to the robbers. It can also be that someone watches you to get your cash, then follows you to steal it. I love Brazil, but that unfortunately is true.
That being said, it is still a good idea to use only indoor ATMs, such as in shopping malls and airports. And be discrete at all times when dealing with cash.