Yes, contact your host. I had the same problem, and ended up changing my host. Try scanning your control panel to find out if you can upgrade PHP. Good hosts will oblige, as it is important to them that they can provide other services dependant on php such as the latest wordpress, Drupal and joomla.
I asked this host and they obliged with giving me and now everyone else a one-click install moodle on their control panel.
http://gogethosting.co.uk/
Also you can install Moodle from hostgator, I also informed them I had a problem on installing moodle, and they obliged by infoming me that I now had a moodle 2.71, and yes I had a moodle 2.71 as claimed.
there are simple tutorials on how to install the latest moodle on youtube. It's important to have the latest moodle, because you need time to get used to working with moodle, before you are forced to the need of an upgrade, which on reflection of other experiences on this forum seems to be more complicated than a fresh install.
http://www.hostgator.com/
I would be interested in hearing what response you receive from your host.