I would appreciate if anyone could help me out with this.

Using:
* linode 512
* ubuntu 9.10
* nginx+fcgi
* default dhcp
* using http://firehol.sourceforge.net for security (easy config)
* default linode IP: 88.88.88.88
* brand-new linode IP (not private IP): 99.99.99.99
* default gateway IP for this linode: 77.77.77.77
* second gateway IP for this linode: 78.78.78.78

My domain is: example.com currently on 88.88.88.88
and things like http://88.88.88.88/hello.php are working
(example.com/hello.php & 88.88.88.88/hello.php = same)

I have a new domain: example.net
I would like to run this domain on the 2nd IP (99.99.99.99)
and http://99.99.99.99/hello2.php should work
but http://99.99.99.99/hello.php should return 404


step 0:

get new IP using Linode manager

step 1:

/etc/network/interfaces
-------
auto lo
iface lo inet loopback

auto eth0 eth0:0

iface eth0 inet static
 address 88.88.88.88
 netmask 255.255.255.0
 gateway 77.77.77.77

iface eth0:0 inet static
 address 99.99.99.99
 netmask 255.255.255.0
 gateway 78.78.78.78

step 2:

/etc/init.d/networking restart

step 3:

#http://forum.nginx.org/read.php?2,2479

server {
   #default linode IP
   listen 88.88.88.88:80;
   ...
}

server {
   #second linode IP
   listen 99.99.99.99:80;
   ...
}

step 4:

reboot

step 5:

#ping all ips and gateways
ping 88.88.88.88
ping 99.99.99.99
ping 77.77.77.77
ping 78.78.78.78

step 6:

...

Not working.

In your first server definition, you have

listen 80;

I guess this makes ngnix listen on port 80 for any IP, and serve the first site everytime.

Try removing that.

@tinono OK, I fixed that and rebooted, I think it could be a problem with fcgi

What does not work? Can you see plain html pages at those virtual servers? What are your fcgi starting scripts? Do you use spawn-fcgi for that?