Just started playing Demon's Souls again. I played through the Tutorial area and then went to the Nexus. I didn't bother going to speak to her and just ran straight through right up to the Phalanx boss.
I thought I'd utilise my souls at this point and go back to the Nexus to make the battle easier. However, I can't find the Black Maiden anywhere to trade my souls. I have searched every inch of the Nexus that I am currently allowed.
I always remembered her sitting down on the stairs on the arch stone to Boletaria, or laying down on the floor on the opposite side?