Diving:

Certify her in Florida, dive some springs and EPCOT, then consider having her dive in the sea. Don't do the quickie resort dive for her. That's a professional Divemaster recommendation. Maybe dive the Bahamas with Stuart Cove.

Locations:

Hmm...Kauai, Costa Rica, and Martinique come to mind. But for the scenery, not the diving.

Matt - you would really honeymoon them in Havana? Gotta wonder about you...

There's also the minor hurricane risk of a July Carib trip. I say "minor", even though there's a Belize 'cane in the news right now, but for a honeymoon it's something to think about. Hurricanes have never deterred me from traveling to the area (or the U.S. Gulf Coast for that matter) - odds are slim you'll run into one. But I might have erred more on the side of caution for the honeymoon...

In fact, I've purposely booked trips into such areas during hurricane season - sweet hotel deals to be had ^ - but they were trips where it wouldn't have bummed us out too hard if they'd gotten cancelled. Trips where my max risk was maybe an airline change/redeposit fee.

We just returned from the Amalfi Coast. Had we not honemooned in Greece, that would have been an amazing place to be. Your AA miles will get you to Naples via codeshare on IB or AB (stay away from BA and the crazy fees). Problem is staying there. We stayed at the Hilton Sorrento so your Hilton Points will cover a few nights, but Sorrento isn't exactly the coastal towns of Positano or Amalfi where the honeymooners we met were staying. Sorrento has it's own charm and the city stays up til 11:30 at night. There were lots of couples at the Hilton, but there were also a ton of families. Hawaii would be nice too and your Hilton combined with the Marriott points will go further there. Though I think Europe is closer than getting to Hawaii from MCO via AA. Depending on how the Euro holds up, it may not be cheap like Costa Rica would be. As much as my husband loves vacationing around Europe, I have been begging him to take me back to Hawaii ever since we got home from our first trip in May. You can't go wrong with Hawaii.

I have no travel experience in any of the areas you mentioned, but in the past year I've gotten into the points game in a big way so maybe I can offer some more objective advice.

As jkoenig51 said, your real strength BY FAR here are your Marriott points, so I would build a trip around a good Marriott property. Having a nice resort/location really sets the mood for a honeymoon, more so than which class you are flying for 4 hours before arriving.

You could conceviably do a 4-day AXON award if you got a few more Hilton points and you have the Amex Hilton Surpass card... but it's a little late in the game for that. I would just use your hard-earned Marriott points and be done with it, book this early and you should get something good.

I would definitely hunt around the Marriott forum, see what the redemption options are, and read reviews online fo the Marriott properties in those areas that you are interested in.

The other big problem I see is that while you have a decent chunk of airline miles, they are all spread out in different programs. The Amex MR points don't transfer to any of the programs you've listed here, so they won't help you pool points. You don't have enough points in any one program for first class r/t tickets to anywhere but within the USA basically. I would recommend strongly against booking with separate programs (e.g. booking your ticket with US miles and hers with United) because if something happens you might have a hard time dealing with IRROPS or other such eventualities.

So basically you are limited to continental US unless you use your AA miles for coach flights to Hawaii/Carribbean. So I would plan on flying AA, to one of the destinations with a good Marriott property.

Simple logic and you've probably thought of that, but if you want to book far out it's too late really to get other points to try to make something else happen.

The key question is where do *you and your fiance/wife* want to go. If you're not looking for long flights then that rules our Asia & Pacific options. So you're looking at domestic/central america/direct flight London/Paris/etc.

Do you want to go to Europe? Do you want to have warm weather and water? Or do you want to explore cities and museums?

For diving, I'd consider Curacao. Depending on where you stay there may or may not be much nightlife, so pay attention to locations. Aruba is Ok for diving and has more activity from what i've heard. Don't do Bonaire as that is pretty much diving focused with not much nightlight. You could do Cozumel or Grand Cayman for both diving and other activities.

Absolutely!

My own I planned using Google Maps and my thumb.

Flew into Joburg, overnight, flight to Pemba Mozambique for diving (and a wonderful pod of wild dolphins was a plus).

Overlanded to Tanzania (using my thumb expected a 6hr journey that became 16hrs) had to bribe immigration at the border, go from bus to pickup truck to boat (had to carry boat due to low tide) and then 7miles on the back of a local guy on a push bike. Got stuck in Tanzania with no cash, Kenyan tourist hooked us up with a hotel for the night and took us to the local airport to fly up to Dar Es Salam for a 3 day safari, robbed by trickster in Dar of hotel for Zanzibar. Got through Safari and onto Zanzibar and dropped at hotel that shut down 6 years prior (thus confirming we got trickstered) checked in next door at an awesome resort, more diving headed downtown for annual musical festival and 5 dollar lobster.

Flew back to Joburg from Dar, decided 8hrs was enough time to check out the Cradle of Humankind, got lost on way back, missed flight, checked into hotel near airport, went to dinner, forgot to pay (signing the check thinking we had given card already) caught next day by waiter who frog marched us over to restaurant (he was accused of stealing the money for bill) paid bill, explained it was honeymoon.. had entire waitstaff of 20 sign local tribal songs and play music for us. Flew home.

I got a bit better since then at planning, but trust me that was an awesome honeymoon!

I just got a headache and knots in my stomach from reading that and the word "honeymoon" in the same story. OP, start researching relaxing Marriott resorts now, unless your fiance wants to ride a pushbike.

If you can get 2 weeks or more, go to Hawaii.
I honeymooned there (on 3 islands) and we were hooked, have been back 6 times in 10 years. We also have been to most of the Caribbean Islands, and while they have their own charms there is nothing to compare to Hawaii.
It is truely a destination you will remember your whole life. Most people start doing calculations on how many jobs they would need to move there after their first visit. Given that your young, you havent been spoiled by first class yet, get a pair of coach tickets flying into HNL(oahu) and back from OGG(maui), catch an interisland flight after a week and try both islands.
It is totally worth the 10 hour flight, you will go back again. If you can get more AA miles go first class, it makes a big difference on such a long flight...but be warned you will be spoiled and won't want to do it in coach again.
You and your wife can dive or just snorkel (best stuff is in the first 35' anyway) Hawaii has more varieties and more fish than i've seen in most of the carib put together. and you can go right from the shore.
So many other things to do and see, and no passport needed.
Only worth the long flight if you can go for 2 weeks or more...otherwise Caribbean is your best bet.

I agree with getting her certified...but disagreed with Kauai only for scenery! Had some great dives there with Fathom Five. Can't wait to go back. Much better than the Carribbean dives I've done. I'd really suggest she take the time to get certified between now and the honeymoon.

Although it's 10+, I would do Bora Bora/Maldives since I've heard such great things about them.

You have so many Marriott points that I would consider a destination that has one of there hotels. Maybe think Hawaii or something tropical

Could do with a few more miles to help smooth that out though...

Can get 45K MIA-LHR-MLE on BA Coach and almost enough to come back in biz on *A if booked using United and US Air separately...

No Marriot there yet though??

Could get HHonors Surpass Card sign up bonus to kick over the 145K mark and get a 4 night AXON7 at Conrad Maldives, but then what?

FWIW when I go there I am going out on UA Miles from JFK in Biz for 60K Each, 4 Nights in the Conrad, hopping over to Sri Lanka for some more hijinks then back on CX Business CMB-HKG-JFK for 95K BA Avios Each. Just need to book a cheap flight from MLE to CMB.

I wouldn't want to fly that long in Coach though, but I am getting spoiled...

OK, that trip was awesome, but it was not Havana.