I have seen this error also on both IE9 and Firefox. The Paypal developer forum had an entry concerning product or vendor images included with the cookie sent to Paypal as a possible cause for the cookie exceeding the maximum size.
Following this suggestion I tried removing the images from my product entries and so far I haven't seen this problem again. Hope this might help!
