I installed the full 1.5.3 theme package on a new website. However, I am getting some issues with Prestashop and tried to upgrade to the latest version (1.5.6) with 1 Click Upgrade. No matter what version I try upgrading to though, the front office is completely messed up with the left column now on the right side and various other modules missing and out of place.

I checked all the module positions and they are correct and the modules are enabled. What could be causing this? Do I need to update the theme as well?

You should download new version from our server now, it's upgraded to 1.5.6 version

Regards