It doesn't matter where you go, but you might want to make reservations. That's a big night for the romantic locals. I know that we did 2 seatings, and were totally booked 2 weeks ahead. About 50% were locals.
BTW, the new name for the Restaurant at Caribe Island is "OVA DI WATA".