Wow I can't believe all of the responses this has gotten in the last 18 hours. I don't even know where to begin as far as formulating a reply. I wish I had some more airline miles and/or more time to get some more. It sounds like my best bet is definitely going to be using my Marriott points, possibly for one of their travel packages. Using one of their travel packages would get me airline miles, which I could hopefully combine with one of the other airlines I have miles with in order to get a first class ticket. So I think Hawaii might be the way to go for now, and try to build up our balances for an international trip for a 1 or 2 year anniversary.

Thanks for all of the replies, and any other advice you might have is greatly appreciated!

True - there is good diving in Kuai, but the scenery is the main attraction. Nice canyon, and if you love chickens...

Compare that to say Cozumel and Grand Turk where the diving is more the main attraction.

As I'm looking at your miles you might want to look at your future CC plans.
I would recommend SPG,Chase Sapphire and Amex Hilton Surpass.The SPG and Sapphire will make you have more options, and can add miles where you may be short. The Surpass will top off your Hilton points and give you gold status and give you access to AXON rewards.(4 nights @ cat 7 145,000).
Also, I'm not sure how or when you got those AA miles but Citi AA cards can be redone at 18/20 months. AA has nice first class service to Oahu 75,000 miles each with a 10% rebate if you have their CC. Both UA and AA allow one way awards.
I traveled the Caribbean for 20 years and then I went to Hawaii,now I go to Hawaii 3 times a year.Don't get me wrong I still love the Caribbean, but when I went to Hawaii I found many things I liked.
1.I spoke the language fluently
2. It was not expensive
3.My cell phone worked
4. My CC worked
5. I was not leery of renting a car
6. My health ins and car ins worked
I don't want to start a debate over which is better Hawaii/Carb because I love both.

This is exactly how I feel about Hawaii too. My first trip was in May. I came home and could not believe that such an interesting destination existed in the US and why had I never gone there? We are so much closer to the Caribbean being in NYC, but I am hesitant to check it out. Thanks to FT, I figured out how to use stopovers on AA and am sandwiching Hawaii between our one-ways from and to Europe. This way both my husband and I get what we each want - he gets a summer vacation in Europe, I get to return to Hawaii.

Yep...I'm a "scanner" so that's why I prefer Hawaii. You can dive, but there are so many other activities (canyons, chickens, brewery....what else does one need??). It's not dive 24x7, and it sounds like the fiancee is probably the same. Might enjoy diving if she gets certified, but wouldn't want the honeymoon centered around diving.

One of the best dives we did was "the Icebox," so called because everything is there. We saw turtles, etc. Our only disappointment was that we weren't there during the whale season...supposedly you can hear their songs for miles. No, I'm not one of those "hey, there's a whale, let's dive near it" but would like to hear them.

Hawaii is generally a good place to use the Marriott Travel Package, since all hotel rates there tend to be high-ish to very high in all seasons. (That is, summer isn't hugely offseason there like it is in some other tropical destinations.)

In recent years, the mileage costs to redeem F to Hawaii have gotten far too high for the product you get. (It's glorified domestic F.) I'd either look for a coach award or look for reasonably priced tickets and save the miles for the Europe/Asia trip where you'll get a truly memorable F product if you pick the right foreign carrier.

But if you're casting the net as far as Hawaii, I'd also throw that Greece idea upthread into the mix. Then I *would* look to redeem two F awards if you can get 'em on a good Star Alliance carrier like LH or LX - or at least two J. If you're locked into Oneworld, I'd look for J on IB metal only.

In Europe, I might not actually use the 7 Marriott nights...might mix/match shorter award stays and even paid boutique stays. Kind of depends on your preferences/tastes... Lots of options.

A most excellent point. I've been to Hawaii three times and love it! All your bulletpoints make for a nice leisurely yet exotic vacation.

A honeymoon couple who may not be experienced in the nuances and potential/likely frustrations in international travel (to less than fully developed areas) might have a better time in Hawaii. I'm experienced in dealing with all the hassles, but I still appreciated Hawaii for your reasons exactly.

To the OP: if you have a year then both you and your fiancee can apply for several CC's and substantially boost your mileage and/or hotel balances in whatever programs you want. It's easy to book a hotel stay partially from your account and partially from your spouse's account. Obviously I would focus on Marriott/Hilton since you already have a starting place. Hotel cost will likely be the greatest expense, so focus on that. If you end up doing Hawaii you could pay cash for a one way flight and miles for the other direction if needed. Maybe boost the CC miles and try biz/first on two different airlines since both AA/UA do one way award flights.