I have followed Baltimore's message and burned the bushes, to get to a door. It keeps saying Key Required. I do have the key, but it just won't open.

What am I doing wrong?

In three Iorveth playthroughs I haven't encountered a bug on this quest. Are you sure you followed Baltimore's directions correctly?

The key you find inside Baltimore's house in Vergen actually unlocks a chest located next to the entrance to the harpy lair (at the quarry). Inside the chest there's another key that opens the door next to the shipwreck, which is probably the door you mentioned in your post.
Hope this helps...!