What is the bin packing algorithm you use? Just curious since I did research on that topic a few years back (results available on my website).
I read lot of articles but following 2 helped me a lot. Especially the first one which gives good idea but the implementtion is up to you:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.200 (click the pdf icon)
The resulting algorithm seems to be similar to what you have on your page - after placing any rectangle I am also tracking all possible new rectangles and for next sprite I am choosing the smallest one from these. I am starting with one big bin - tower of sprites with width of the widthest and changing (see the rules in linked file) step by step to one long row with hight of the highest sprite. There are also always severeal tries in each "bin" incorporating some chance in sorting the rects but generally the biggiest are placed as first.