Well … sorta. I can’t upload any size of image, but previously I was limited to about 0.3MP (640×480). Now I can upload up to about 1.5MP without the dreaded Memory error. I can also use WordPress’s Auto Upgrade feature again.
Daddy Hogwash’s “WordPress 3.0 Upgrade Complete after Solving Fatal Error: Out of Memory Issue” is what fixed it. His suggested number of 40M fixed the auto upgrade problem, while I upped it to 64M to get larger images to work with my host, 1and1.com.
Update: There is no fix for this. Memory limit on my kind of hosting is ~34M. Any higher is not allowed. This seemed to work for a while, now doesn’t.