My bet would be, that you have disabled memory management for some qubes or have set the initial=max memory for them.
Since I was memory-curious i made this widget to show memory usage.
To test your statement i started off with :
9 / 30 / 32
Starting a 20GB init=max qube without balancing fails due to:
Same with 18G init=max :
27 / 31 / 48
With 10G init and 32G max + balancing :
19 / 31 / 61
Try it for yourself - worst case, @Euwiiwueir is right and your system really uses too much ram.