I just tried to add a private IP to my Linode (as described in the Network tab of the Linode Manager). As usual, I created the virtual interface eth0:0, here is /etc/network/interfaces:

....
auto eth0:0
iface eth0:0 inet static
        address 192.168.136.xxx
        netmask 255.255.128.0

ifconfig:

eth0:0    Link encap:Ethernet  HWaddr fe:fd:48:0e:ba:c9
          inet addr:192.168.136.xxx  Bcast:192.168.255.255  Mask:255.255.128.0
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1

route:

Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
72.14.186.0     *               255.255.255.0   U     0      0        0 eth0
192.168.128.0   *               255.255.128.0   U     0      0        0 eth0
default         gateway52.linod 0.0.0.0         UG    0      0        0 eth0

I did restart the server and the networking services. Howeer, this seems to not work - if I try to access my other linode, i keep getting "No route to host" or "Destination Host Unreachable" errors.

FYI - your IP address is encoded into your MAC address, so if you're paranoid you're going to want to mask that out too.

Are you sure the other linode is configured for the private network properly as well? I don't see anything immediately obviously wrong with what you posted...

Also, check your arp table (arp -n) to see if it's seeing the other linode at all...

We'd be able to better assist you if you open a support ticket. Unless I'm looking at the wrong account, I only see one Linode. Is the other Linode you are attempting to contact located in the same data center?

-Tom