AFAIK, Ubuntu use the Debian packaging system unchanged, apart from their own repositories.
My first instinct is to ask if you're using a /boot partition and if so, is it a bit short on space. I got similar errors on another box when /boot was too small.
Wade.