Allen,
I was supposed to depart on a trip to Grenada (going through the Bahamas) this Saturday in the Mooney. My friend is starting med school down there, so we were going to make a fun trip out of flying the thing down, island hopping, and dropping him off. We ended up having to cancel the trip because the Mooney's insurance wouldn't cover it. We're rescheduling the trip for something in probably June or August (either when he comes home for the summer or needs to go back for the fall), and we're going to take the Aztec this time. The Aztec is not only a better choice for the trip, due to its larger size and much higher useful load, I'll be able to bring some more friends along so I don't have to fly home solo.
I started a thread with my experiences and what I found, you can find it here:
http://www.pilotsofamerica.com/forum/showthread.php?t=24256&highlight=grenada
The biggest legal things off the top of my head are:
1) Make sure that your insurance covers it!
2) Make sure to get your radio licences, both for the plane and for the pilot
3) Order your DTOPS user fee decal (a customs requirement)
4) Order the appropriate charts. Jeppesen makes a full Caribbean travel kit (IFR), which I bought and I think is a worthwhile purchase. You can also get the VFR WAC charts, which I bought as well (I like having both)
There's more, I'm sure, but I can't think of it off the top of my head.
AOPA's resources are decent, but I was happier with the service I got from Jim at Caribbean Flying Adventures. He's got a fee for use of his website, but it's worth it. There's a lot of good information on there, including fuel prices.
Your $3-4k total budget sounds reasonable to me, especially given the fact that your plane burns so little fuel. I would expect you to spend less than that, actually. It seemed that we were going to spend about $5k on the trip to Grenada (round trip) coming from New York in the Mooney. Figure in the Aztec it'll be more due to the higher fuel cost.
Allow a few months between start of planning (today) and when you plan to take the trip, as a number of these things may take some time. I ordered the DTOPS tag about 3 weeks ago for the Mooney and haven't gotten it yet. I pushed too close, and it may not have arrived in time for my trip anyway. I am thinking I should order the one for the Aztec now, just so I have it, but I'll wait until I get all the official paperwork back from the FAA.
Good luck!