We haven't set a weight in the past for any of the products and it was working well.
I had a premier session with Webassist where a custom postage was created for this install.
Three options were created when a product was added a price was put into each of the options (UK, Europe, Rest of the World).
This was then passed to paypal based on the users address.
The only thing that I can think (bearing in mind that no code has changed) is that the method for passing the shipping to paypal isn't working....?