Is it worth getting them to do another prototype, just to make sure I get what I want before they crank out 500 of them?
Probably, 500 is a lot to waste or rework.
It depends on how good your existing prototype board is, if you just made 1 or 2 simple changes I'd go the full monty. Any more and I'd get another prototype, especially if you are going to use a different fab house.
Rob