These are pretty rare. I've had one drop for me when I first started playing again. Since then, I've farmed this zone for hours and hours for pelts and skins and silks for tradeskills and I've not seen another one drop. Doesn't bother me since I have a druid who can make Leatherfoot Haversacks at will, just saying.
Dropped last night (July 29th, 2008) in CR off a skeleton out by the farm. Thought it was a new item after the patch since I've never heard of it before.
Was just wondering, why "Magic"? None of the other weight reducing bags have that tag, and it's not a container you can combine in.