If you migrate from Ubuntu 14 to Ubuntu 16, PHP’s version also changes from 5.x to 7.x.
Magento 1.9.x versions seem to work the same at first sight, but e.g. the cart and also the order process is done without VAT.
According to various forum threads, the cause is that sorting has changed with PHP7.
Download this module, it provides a fix for this issue.
Extract it to the root folder of your Magento installation, e.g. /var/www/html.
You might have to delete cache files, afterwards everything should work again.