I had a problem with this in the past. Its quite easy to do with a windows host. But I was unable to do it with a linux host.
I ended up bringing another linux image up, using a bootable linux on both, and dd'ing data from one to the other. it was not an easy process and did not work the first couple of times i did it. There was a fair amount of trial and error.
Of course, by now, there may exist an actual process to shrink a linux host.