Normally upgrading from Magento 1.0.19870 to 1.3.1 should be no problem, as Magento takes care of all the required table changes.  I mostly faced script timeouts on the server in the past, which broke the upgrade process and turned the installation unusable.

I have switched to upgrading customer databases on a local installation, as that allows me to workaround timeouts and prepare databases for the upgrade.

Before upgrading an installation, you should also delete any content that can be recreated by Magento again. Logs, price rule caches …. can all be deleted, as the system can generate those again.

Really sad how everyone needs to piece those things together, as the Magento Community Knowledge Base is mostly outdated and many hints are buried deep inside the forums.

Currently working my way through a huge Magento 1.0.19870 database and will comment on my success once everything works.