I was having some issues on a server where a particular plugin (bb-plugin) wouldn't update, and I'd just get this error:
PCLZIP_ERR_BAD_FORMAT (-10) : Invalid archive structure
After much poking around, I ended up installing the php5-curl package (on debian), and this ended up solving the problem. I think php was downloading the archive from the update server, but for whatever reason it was getting corrupted or not saving correctly. With curl the download seems to have saved the zip file correctly, and thus the error went away. It seems to have only been effecting this one plugin, as other plugins and wordpress auto updates were working just fine.
Anways, I didn't have much luck in googling a solution to this problem, so I thought I'd publish what I found.