Chicken soup for your souls!
I was finally able to get 82 souls on the Port Royal level in the enclosed area with the bar tender against the marines and the commander in the blue suit. I would rev up my special ability bar to 1/4 and then do the special move on one of the regular marines, keeping in mind that I choose the button circled in red. Once I got a skull, I'd lure them up on the balcony area and then drop down to activate the green sword while they ran back down the stairs. I'd then slash away being certain not to kill the commander in blue. Do not die, or you'll have to start over. I got about 10 more souls on the large enclosed area at the end where you raise the gates and pull levers.
I got as many souls as I could on all the other stages so I wouldn't have to get so many on this stage, but I kept going just to be safe. I highly recommend the Port Royal stage as the easiest to get the souls.
As for the Prison Fortress chest, mine had the skulls there when I replayed the level.
(Why is there a stupid "Analogue" gamer tag window on my post? and I am currently #100 in total notoriety for this game.)
Last edited by E vee dub; 02-11-2008 at 09:59 PM.