It's not Erik's bag, actually, it's Mrs. Johnson's ex-husband's. You have to talk to him in jail, and he'll ask you to pass on a message to her. You actually have to pass it on to Erik (the storyline is in the middle of a rewrite), and then Mr. Johnson will tell you where the bag is. It's in the park, behind a bush. When you search the bag, you should find the key, but the game gets screwed up (again, Erik's stuff needs a rewrite) and doesn't actually give you the bag until you're part-way through Mia's storyline so that you can give it to Harold. It should give you the key just fine, though?
Ah, yes, Mia's story is full of nitpicky crap like that, glad you found out what was wrong!