After you get to the arena you jump down a pit to the level where you get a quest from an imp to get a monster's tooth to cure his sick brother.
Well, directly across from the room where you land (missing the haystack as your deathknight "friend" points out) is the bedroll in a small room.
