> nginx would bind to *:80 and not complain that it doesn't have any of the other IPs.
> With nginx 0.6.35 (and 0.6.32) that configuration fails the test, and logs this:

Your error message is saying that it is having a problem binding to port 80 on 127.0.0.1 and 192.168.136.80, not the other IPs listed. Do you have something else already listening on the port? 'netstat -lnpt | grep 80' or similar could show you what has the port bound.