If you are using a WordPress installation along with a WHMCS bridge plugin, the cause is that the WordPress plugin modifies the output of the values sent through to PayFast. In order to fix this, you need to comment out the signature generation part of a file located with your WHMCS modules folder. Go to file, /modules/gateways/payfast.php, and at line 209, comment out the following lines:
//$pfdata['signature'] = md5( $pfOutput ); //line 209
You also need to ensure that the 'Require Signature' setting is disabled on your PayFast merchant dashboard under Settings > Integration > Payment Page Settings.