I like hopping around Micronesia on the 20/25K intra-Asia award (in conjunction with an Asia trip) available through OnePass or WorldPerks. Places like Majuro, Pohnpei and Yap are hard to forget, and you can also get to ones like Cairns or Bali.

Alternatively, spend 50K/60K to get there from the U.S. rather than 35K for Hawaii. You get a free stopover anyway and probably must go through Honolulu, so adding a destination in Micronesia or Asia costs 15K or 25K more (though it'll be 25K after they eliminate the off-peaks)