We're facing problems dealing with banks and we would need some help. We're thinking about starting the company in a bitcoin friendly country like Panama, Uruguay, Andorra, Switzerland, Canada, Poland...
You could set up in those countries, but you have to remember that the biggest market for bitcoin is USD, and if you want to accept US customers which would seem logical, you still need to register and comply with all the same things a US based company would. I'm not sure about EUR, but it wouldn't surprise me if the same were true.
Best thing to do IMO is to seek a partner who already has the relevant US licences and work with them.
Cheers, Paul.