For at least Ubuntu 12.04, the install-wine-deps.sh script specifies a library as follows:

libhal-storage-dev-dev

on which my system chokes. Removing the final -dev to yield:

libhal-storage-dev

works fine. Other versions of Ubuntu in the script show the same reference which may or may not be problematic. Don't have them, can't test.

Cheers!

P.S. the script URL is:

http://winezeug.googlecode.com/svn/trunk/install-wine-deps.sh