Memory Error

I’m having a huge problem with my WordPress installation. Shortly after upgrading to 3.1.1, I started to see errors like this all over the place.

“Fatal error: Out of memory (allocated XXXXXXXX) (tried to allocate XXXXXX bytes) in XXXX.php on line XXX”

I can’t even access some pages of my dashboard because of this error, and basic functions, like adding posts and pages, don’t work.

I’ve contacted my host, and they’ve done everything from edit my wp-config file to increasing my PHP memory limit to 128M. I’ve tried a plugin, that didn’t work.

Any advice?