So lately I've been looking a lot into the legalities of bitcoin and bitcoin exchanging and I haven't been able to find exactly everything I'm looking for on the matter and hoping someone on here can provide some insight that I may be overlooking. Me and a good friend of mine have been trying to look into starting a website in which we would do exchanges of bitcoin and other cryto-currency stock that we already have for mostly PayPal. With that, we've also been considering registering as an official LLC (Limited Liability Company) with the reasons being so we can efficiently handle the tax implications that come with bitcoin and for other official reasons to establish ourselves as exchangers. My biggest question would be this; if we were to proceed with this and registered as an LLC, would we be required to obtain Money Transmitter Licenses in every state that our clientele came from? I've also found articles explaining how areas of the government, like the IRS, consider bitcoin to be property, and not considered a currency because it is not backed like the USD. I also know that very well known websites, such as CoinBase have these licenses in every state that requires them, however, others, such as CEX.io and Kraken do not. I'm at a halt in what I can find right now, so any information would be greatly appreciated. 

The legality of Bitcoin exchanges is very hazy in a lot of countries, but generally they are legal and not too heavily regulated.

However, some exchanges (such as Coinbase) have introduced some pretty draconian measures for verifying your identity and this could be interpreted as the American government acting harshly as Coinbase mostly operates in America.

Most exchanges are OK when dealing with small amounts, especially the major normal exchanges (Coinbase is a tad unusual), like Bitstamp or Bitfinex.

You are right in saying that Bitcoin is seldom classed as a currency by governments.  Usually it is classed as an asset/property and due to that it is regulated less and arguably this makes it more convenient to do Bitcoin transactions.

Anyway we come to the most critical point about the progress of bitcoin, in some countries decisions contrary to the government have increased use by bitcoin, but on the other hand has decreased membership for new companies.
No businessman will try to provide a service against the government, unless he wants to answer for various legal actions. Cases such as Coinbase clearly show how fragile bitcoin is as currency in regulatory issues.

The legal status of Bitcoin exchange is very misty and it varies from country to country. Some countries prohibit the exchange of Bitcoins but on the other side, some countries give a legal or not too heavily regulated viewpoint to Bitcoins. Many countries have Bitcoins ATM machines and you can easily make a transaction.