Oh don't you just love cryptic error messages that could mean one hundred and one things? Yeah, me too.

So in the interest of some poor soul (maybe it's you ;-) searching on this topic in the year 2142 I decided to point out what resolved this issue for me.

Background: I am running Windows Server 2008 R2 with IIS inside a Hyper-V instance. The VM was configured with a static IP and each IIS site was configured to bind to that IP, and that IP alone.
I transferred the VM to Amazon EC2 (using the ec2-import-instance API) since I wanted to move away from having to maintain my own physical hardware. Long story short, once transferred I was unable to start any of the IIS sites, they all failed with the error 'The format of the specified network name is invalid - Error 0x800704BE'.

I knew that this error was likely related to IP bindings of some kind (EC2 usually expects you to use DHCP for IP address assignment since even an elastic IP can change) so I tried binding a few IIS sites to 'all' IPs. Still the sites would not start, but throw the above error.

I dug deeper and used the netsh utility (Windows commandline) to show which the network configuration for the machine, and in particular which IPs the HTTP service listens to:

view plain
1netsh http show iplisten

This listed just one (the previous static) IP of my VM - this was now wrong. So I removed the binding with

view plain
1netsh http delete iplisten ipaddress= (where is the actual IP that needs removing)

Next set the service up to listen to all IPs:

view plain
1netsh http add iplisten ipaddress=

I then restarted IIS using

view plain

and bingo, the sites started to work.

Hope this helps someone.