Is there space for me on your team?
I have spent most of this year trying to answer the same question, starting with the recognition that I could solve all the technical aspects (web programming, Bitcoin handling, trading engine, server security, etc.).
Technically, you need a website and a trading engine that matches buyers and sellers. Whilst there are lots of pitfalls---I cannot imagine a better target for cybercriminals than a bitcoin exchange storing lots of online withdraw-able virtual and real currency---all of this has adequate solutions. Not easy ones, as the technical problems occasionally seen at competitors appear to include layer 7 DDOS attacks and some have fallen pray to not storing their clients' bitcoin securely offline (and with adequate internal handling protocols), but this is really not the part I'd consider difficult to do better. To give pointers: Bitfloor is a company that fell victim to this (going out of business over it), whilst MtGox experienced it yet was able to stay in business.
The key problem is the legal aspect of your operation. The bitcoin exchanges you mention work slightly different then, say, an online stock market exchange. The later will basically negotiate contracts, leaving the participating financial institutions to settle these. It all needs lots of regulation to work, and even so the regulators (e.g. the SEC in the U.S.) are needed all the time to settle and fine disputes. Bitcoin exchanges usually require customers to make deposits. This avoids the settlement risk, but, in the eyes of many regulators (not just the SEC, but, so far and in the U.S., FinCEN and state agencies) puts them in a category with money transmitting companies like Western Union, for which there exists alot of costly and time-consuming licensing requirements. The basic idea is to safeguard customers from mishaps at the company, guaranteeing that there is money to pay them from. Today's law enforcement appears to go significantly beyond this rationale behind the law; in the case of MtGox, a US-bank account associated with them was seized for forfeiture to the government for unlicensed operation. You might think this perverts the idea of protecting the customer from a loss of those funds. I've looked into legislation in the U.S., Germany, and the U.K., and it seems that out of these, only with customers from the U.K. at least the national regulator for the money transmitting aspect does not jump to the view that you need a nearly unobtainable license (status as of this spring, with a warning that this view might change if Bitcoin were to grow so much that it would start being used "as money").
Next, you are potentially exposed to alot of fraud. Bitcoin works so well in being final and potentially anonymous that it seems to attract criminals who manage to make banks transfer money but need a way to launder such funds. You can expect that banks will start to notice a statistical association of your business with frequently disputed or outright illicit transactions. Several bitcoin exchanges have lost their bank accounts, presumably over this kind of issue, including MtGox' original EU bank account, Intersango's UK banking, and bitcoin-24's German banking. Fortunately, I think I have read articles claiming that three banks (in Silion Valley, NY, and Munich) have come out as supporting bitcoin exchange businesses if they implement rigorous anti-money laundering rules. I don't have links ready but could probably find them quickly.
Finally, you'll need someone to understand and deal with anti-money-laundering rules and anti-terrorism financing. When I read the laws about these, it sounds to me that you have to do just about everything that you'd think any democratic constitution would prohibit, like spying on your customers, acting on suspicion, keeping parts of the government well-informed and lying to other parts of the government. I'm not joking; see another answer from me. However, these rules obviously have a good reason, and that is not to allow any terrorist, criminal, UN-sanctioned person or entity, etc., to move money or related things of value. I suspect with a bit of guesswork they also explain some of the beef some banks have had with bitcoin exchanges in the past, and their tight-lipped attitude about it.
If it needs spelling out: Following anti-money laundering rules includes identifying your customers (often in the UK way of requiring photo ID and a utility bill), making sure they come from places you are licensed to do business in, checking that they are not on a blacklist, ensuring that data you could be expected to look at do not make them look suspicious. This, and the change of perception of Bitcoin by regulators from something not worth noticing to something to keep an eye on seems to be reason why the existing bitcoin exchanges now all require ID.
I still want to build a bitcoin exchange or a functionally similar alternative. But I need support in dealing with all the legal aspects; getting it right or raising the large sums of money and having the 2 years or so patience for getting licensed in larger US states is beyond what I can do on my own. Again, is there room for one more in your team?