Make sure that you have installed the current PayPal Patch and uninstalled, reinstalled and reconfigured your payment module:
http://www.zen-cart.com/forum/showthread.php?t=56216