Not being able to select costume IP to launch multiplayer server from singleplayer sucks!!!
Also minecraft on linux selects 127.0.0.1 as lan IP and it should be something like 192.168.1.56!!
Linked issues
Comments

I believe the problem is that in linux it binds it to 127.0.0.1 and other people on the lan cannot connect to that.

It doesn't matter to what IP the server is bound, from the server-hosting PC itself the server is reachable at 192.168.1.56, 127.0.0.1 or localhost, for the rest of the LAN the server is reachable at 192.168.1.56
This is true. I have seen this twice though in here, which is odd. I just ran a test on CentOS6 and it binds to *:25565. Unless these guys are updating their serverip line in server.properties. I don't know how this is breaking. The only other issue would be related to firewalls.
Should the localhost issue be reported as a separate bug, seeing as it is, well totally separate to the bug mentioned in the title.
It DOES matter to which IP the server is bound because the IP specifies the interface and localhost is not the same interface as Ethernet. Services which are bound to all interfaces are shown in netstat with a * instead of an IP address. Also you talk about binding to *:25565 - that's the server, the client's publish-to-LAN functionality doesn't use that port.
I have discovered some more about this that may be a work-around to Linux users and possibly a clue to developers: The IP address selected is the one associated with the hostname, as returned by the command line ("hostname"). And this may be affected by your hosts file (/etc/hosts). So for instance I had the following in my hosts file (/etc/hosts)
127.0.0.1 localhost
127.0.1.1 westy3
These lines were written by the OS installer, and westy3 is the name I gave that computer at install time. Minecraft was binding to the second address. I now comment out the westy3 line like so
127.0.0.1 localhost
#127.0.1.1 westy3
and the problem is fixed. Some more command output for your info:
dave@westy3:/opt/minecraft$ hostname
westy3
dave@westy3:/opt/minecraft$ host 127.0.1.1
Host 1.1.0.127.in-addr.arpa. not found: 3(NXDOMAIN)
dave@westy3:/opt/minecraft$ host 172.20.21.103
103.21.20.172.in-addr.arpa domain name pointer westy3.
dave@westy3:/opt/minecraft$
You see now the computer name is associated with a LAN address (a Bluetooth connection as it happens) and hey presto, Minecraft's publish-to-LAN now binds to this address. (At some point I'll confirm on a real LAN that this makes the game accessible, but I'm 99% certain it will).
The behaviour can be seen in Java outside of Minecraft:
System.out.println (java.net.InetAddress.getLocalHost().toString());
which prints different IP addresses according to the various circumstances already described (ie Windows vs Linux and modified /etc/hosts)

Fixed in 1.4.4
If your PC has 192.168.1.56 than is 127.0.0.1 the same, because the latter means localhost