All govt warnings are designed to protect the *** of the govt, they offer virtually no real tangible advice.
The Indonesian govt has gone to great lengths to counter the terrorism problem in the country (with a lot of assistance from the Aussie and US govts). The problem has stemmed from a handful of radicals from Java who were indoctrinated and trained in Pakistan and Afghanistan, they have trained a new generation of militants to conduct their 'operations'. The govt has arrested over 300 terrorists, and CT operations continue until this day.
Bali is a Hindu island, not Muslim, but there are small Muslim communities who pose no threat to security. The bombings in Bali were conducted by indoctrinated Javanese Muslims, who saw the island as a land of hedonistic infidels, etc, etc..there will always be a risk especially in Kuta, Legian and Sanur. However, the real diving is done in Padang Bai and Tulamben, both of which are 1-2 hrs north of the main tourist areas and are in small fishing villages, heavily populated with Hindus.
Ambon (the capital of the Maluku Islands) was the scene of a sectarian war between locals (Maluku was a Christian majority) and Javanese Muslim radicals, who were actually sponsored and trained by the Indonesian Army Special Forces. The sectarian conflict there and in neghbouring Central Sulawesi was orchestrated by the Army after the downfall of the Suaharto regime (in 1998).
The president at the time was 'Gus Dur', a moderate Islamic cleric who openly pledged moderate Islam and secularism. Certain leaders within the military heirarchy hated him for this and created a war in order to humiliate him and make his tenure ungovernable.
There are still elements of radicals and also Moluccan seperatists in the area, sporadic violence still occurs, but it is much safer than before. Doing a lb in the area should be ok, if you are staying in Ambon, stay off the streets of Ambon city at night to be sure.
As previously mentioned, the main risk throughout Indonesia is actually via poor hygiene and infrastructure, there have been 2 major 737 crashes, two ferries sinkings, and several train derailments this year alone.
It is a third world country run by third world leaders, they simply don't care. Be especially careful when travelling on the roads, Indonesians have no idea about safety, nor do they employ common sense when driving.
Having said that, they are genuinely friendly, not hostile to foreigners (providing you are not a dickhead) and the diving is fantastic.
enjoy.