Hmm, php5.anything should be good.
What is the max_execution_time value in the phpinfo? If it’s really low (<30) that might cause problems.
I’m out of ideas though. This is a “generic” WP issue with plugin activation so some more Googling might turn up other ideas. I searched for “wp 500 on activate plugin”. The 500 is the Internal Server Error code.