Well to me the worst parts about POTC are Will and Elizabeth while the best parts are Jack, Barbossa and Davey Jones so I am all for a Prequel.
There is enough backstory that has been mentioned throughout the movies to fill out the story. The mutiny against Jack was only 10 years before COTBP so there would be no need for recasting any actors. Also like someone else mentioned there would be roles for Bootstrap Bill, Tia Dalma, Cutler Beckett, Pintel and Ragetti if it was a prequel as they were all around before COTBP.
As for the title I would make it like the Indiana Jones films and call it "Jack Sparrow and the ..."
If Gore Verbinski doesn't come back I'm sure they could find a good director for it. How about Johnny Depp's pal Tim Burton. He could make it a bit darker and more quirky then the main trilogy plus in the last few years he has been making a few lighter films. He has also worked with the DOP and Production Designer of all 3 Pirates films if that means anything.