I know this is a rather late reply I have only just logged onto LonelyPlanet. The comment in one of the posts in response to your query that Wakatobi Marine National Park is hard to get to was by someone who admits to never having been there and does not know anyone who has. Consequently the comment is of no real use so I thought I would let you know from my experience which dates back to 1996-2000 and again more recently this May-June 2011.
In the past it did take some time and effort to get to the Tukang Besi Islands and one had to rely on a variety of slow local transport such as the PELNI ferry and then small local wooden ferries. Also there were only two options of places to stay and dive: Operation Wallacea (a research outfit) on Hoga Island or the expensive, but very nice, dive resort of Wakatobi Divers.
However, now not only is it quicker and easier to get to the Wakatobi Marine National Park in the Tukang Besi Archipelago but there are also various options as to where to stay and where to dive.
Getting there: To get there you can fly daily to Bau Bau, Buton Island, SE Sulawesi via Makassar (Ujung Pandang) south Sulawesi from one of many principal Indonesian cities. From Bau Bau you can take one of the daily Express Air flights to the new (about 3 years old) airport of Matahora, Wangi-Wangi Island which is the northernmost island of the group; this flight only takes 15-20 minutes. From there you take a taxi to the Pelabuhan dock, Mola just on the outskirts of Wanci, the main town on Wangi-Wangi where you do the final move, if going to Hoga Island on the speed ferry (2 hours) at about 10am each day. You can also get a ferry to Tomia from there as well.
Flights to Bau Bau are with Lion Air and can be booked direct with them on their website or through a travel agent. The Express Air flights have to be booked locally using someone or a company with an Indonesian bank account. Most resorts are happy to do this for you and you just reimburse them on arrival. The cost of a one-way ticket Bau Bau to Matahora in June 2011 was Rp450,000. Cost of flights to Bau Bau will depend on the departure point, day of week and time of year.
Another option for getting from Bau Bau to the Wakatobi is to take the local ferry either going to Wanci (every night) or to Kaledupa (3 times a week). However the months of June-September/October can be pretty uncomfortable because of the wind direction and the strength.
Diving can be found at several locations:
a) The dive shop in Wanci near the Hotel Wakatobi;
b) Patuno Resort Wakatobi (mid to high end) on the north shore of Wangi-Wangi;
c) Hoga Island Dive Resort on Hoga Island (budget to mid range) next to Kaledupa Island;
d) Alam on Hoga Island (budget to mid range) outside the Operation Wallacea 10 week period June-September each year: phone number only;
e) Wakatobi Divers (high end) on Tolandono (a tiny island next to Tomia which has a private airstrip used exclusively by the resort);
f) Tomia Dive Centre (budget) on Tomia itself;
g) There is also a local liveaboard boat which runs out of Wanci. Phone number only at present but website said to be coming soon.
The diving in the Wakatobi Marine National Park is very varied and very rewarding. There has been a problem with locals stealing sand from the beaches (now banned) which exposed underlying sediment which then gets washed out onto the shallow reefs. In some places (a few) this has killed the upper corals and sponges but the walls are still in beautiful condition as they were 10 years ago. Many places have been completely unaffected by this such as the North Wall on Hoga Island. Diving is not necessarily expensive particularly if taken as an accommodation / full board and diving package. Best to check out each option personally and most have websites or even Facebook pages with full contact details.
Diving in Bali is generally a more expensive proposition and all dive operations there have websites. One very nice resort on the NE coast is Scuba Seraya which is set away from the crowded Tulamben area but still offers dives on the Liberty Wreck plus their own special sites.
Good luck and if you have any other questions, let me know: will try to help.
