This can easily be recreated for me by disabling FedEx shipping method and going to the cart and then enabling it and it gives me 500 error.
Here's the system log from magento. For security purposes I've replaced the domain name with "domain".
2012-10-19T03:57:53+00:00 ERR (3): Warning: include(SoapClient.php): failed to open stream: No such file or directory in /var/www/vhosts/www.domain.com/httpdocs/lib/Varien/Autoload.php on line 93
2012-10-19T03:57:53+00:00 ERR (3): Warning: include(SoapClient.php): failed to open stream: No such file or directory in /var/www/vhosts/www.domain.com/httpdocs/lib/Varien/Autoload.php on line 93
2012-10-19T03:57:53+00:00 ERR (3): Warning: include(): Failed opening 'SoapClient.php' for inclusion (include_path='/var/www/vhosts/www.domain.com/httpdocs/app/code/local:/var/www/vhosts/www.domain.com/httpdocs/app/code/community:/var/www/vhosts/www.domain.com/httpdocs/app/code/core:/var/www/vhosts/www.domain.com/httpdocs/lib:.:') in /var/www/vhosts/www.domain.com/httpdocs/lib/Varien/Autoload.php on line 93
I have installed php-soap via yum but I don't think it's enabled in php because in my php info all it mentions about php soap is the soap.ini file. In that file. soap is uncommented, but I'm not sure that I've correctly added it to the PHP.ini file. I wasn't able to locate the php.ini file but was able to use plesk to add a command for the php file which was supposed to enable soap, but I'm not sure if that's working.
Any help or pointers is greatly appreciated! I've spent so much time on this issue.