If you don't have the appropriate patch some DLCs will not work.. For instance (On the 360) Dead Money required you to have the first patch or you wouldn't get any XP even though the level cap was raised to 35.
Also.. Did you download the correct version of the DLC.. In the EU we get 2 versions, one is for BLES00901 and the other is for BLES00902.
Okay, I say, in the EU we get.. .. But we didn't get Honest Hearts.. It's not on our PSN yet.. Humpf..
Oh.. Even though the DLC introduces a complete outer area to explore the DLC is actually pretty short.. If you only do the main quest that is.. Seriously.. It's REALLY short.. Still.. I like this one more.
Hint: You are allowed to go into the area with 100 max in weight (Weapons/Armor) when you enter the DLC area.. SO they are not stripping you of anything.
Go from A to B.. Collect some goods.. Bring those to C.. Secure a couple of locations.. Back to C.. From this point on the game branches so it's wise to save if you are trophy hunting.. You either kill some guys or protect some other guys and it's over.