error on multisite install

Hi, I am getting the following error while trying to install multisite:

Fatal error: Out of memory (allocated 786432) (tried to allocate 122880 bytes) in /home/appmarke/public_html/wp-settings.php on line 128

I am paying close to $90 / month for the follwing vps setup at


40 GB storage
600 GB transfer

$40/mo (add 15 for cpanel, 30 bucks for managed)

I was surprised that I got this error on install; I am nervous that I am not getting what I paid for from my hosting provider (I am relatively new to this...etc.) but have a full working version of my site on my localhost but will be rebuilding the network from scratch on my server...

Any thoughts?