WordPress out of memory - pay you for a simple answer that works

I am Running a brand new installation of WPMU on Ubiquity VPS.
Config as follows:

MySql version 5.0.85-community
Apache version 2.2.14
PHP version 5.2.11
also see http://methodsofhealing.com/phpinfo.php

According to my support, php.ini file memory limit is set to 512M (which we did trying to troubleshoot - it was 32 and then 128M)

I am running WPMU version 2.8.4a fresh install - put it up last week.

I did copy the database from my old host, onto this new install if that makes a difference.

MU Plugins: Plugin Commander, Cets blog Defaults, and RA remove blog offset.

Regular WP Plugs include: ad minister, adsense manager, AIO SEO pack, featured content gallery, page link manager, redirection, seo automatic links, sitemapXml, smart video, sociable, ultimate google analytics and limit posts.

When I look at my dashboard: In the 'incoming links', 'plugins' and 'WordPRess development blog' areas I see "Fatal error: Out of memory (allocated 16515072) (tried to allocate 19456 bytes) in /home/xx/public_html/wp-includes/class-simplepie.php on line 2221"

When I try to upload a plug-in I get the following error: "Fatal error: Out of memory (allocated 16777216) (tried to allocate 77824 bytes) in /home/xxx/public_html/wp-admin/includes/class-pclzip.php on line 2481"

I have tried de-activating all plugins, but no luck. I even deleted them all together.

I have recently changed hosts, because my previous host was crashing periodically, I changed because the last host was crashing once every couple hours (Linode) - at least the new install does not crash so often, but I can't use my install very well, since it will not let me upload photos, etc.

Another thought is that it could possibly be my theme. It seems strange to me, but I have attached it.

Also, I had considered that there could be a mischievous script running somewhere. Remember this is a fresh installation of WPMU - the only thing that is not new is the blogs.dir and its content.

Please help.