1) 80k miles per person? wow! are you flying El AL?
2) ok so if so--or if flying business or first, then there still could be time if you do presidential coins. yup, Mint coins. They are the current way to earn miles uber. The thread is in MilesBuzz.
3) While it may not be on the same path as you had originally planned, I would suggest both you and the wife to be apply for the AA cards and get at least 75k per person right there. ON AA a flight to Maui is 35k per person but that's econ. But what some do--especially if flying from the East Coast--is try to arrange the trip such that the stop is in Cali. That way you can enjoy some of that state for a tiny bit and then connect onto Hawaii. I mean that's at least how I last did the trip. (ie: enjoy the destination over the flight itself)
Then again I have no idea if any of that applies to your sitch. I'm a mere Red Sox fan and not from Joisey

MM