Unable to add a static route: SIOADDRT: Network is unreachable

I’ve been bashing my head against a wall for a few days trying to figure this out:
My ifconfig is:

eth0      Link encap:Ethernet  HWaddr 00:50:56:BB:XX:XX
          inet addr:192.168.36.132  Bcast:192.168.37.255  Mask:255.255.254.0

eth1      Link encap:Ethernet  HWaddr 00:50:56:BB:XX:XX
          inet addr:116.xx.xx.xx    Bcast:116.xx.xx.xx    Mask:255.255.255.192

When I try and add a static route to go out of eth0, I get the following error:

servername-test:/ # route add -net 10.248.12.0 netmask 255.255.255.240 gw 192.168.36.254 dev eth0 
SIOCADDRT: Network is unreachable

My Default gateway is:

servername-test:~ # netstat -anr
Kernel IP routing table
Destination     Gateway         Genmask         Flags   MSS Window  irtt Iface
116.xx.xx.xx    0.0.0.0         255.255.255.192 U         0 0          0 eth1
192.168.238.0   192.168.36.254  255.255.255.0   UG        0 0          0 eth0
192.168.239.0   192.168.36.254  255.255.255.0   UG        0 0          0 eth0
192.168.36.0    192.168.36.254  255.255.254.0   UG        0 0          0 eth0
169.254.0.0     0.0.0.0         255.255.0.0     U         0 0          0 eth0
127.0.0.0       0.0.0.0         255.0.0.0       U         0 0          0 lo
0.0.0.0         116.xx.xx.xx    0.0.0.0         UG        0 0          0 eth1

ip route list output

116.66.240.64/26 dev eth1 proto kernel scope link src 116.xx.xx.xx 
192.168.238.0/24 via 192.168.36.254 dev eth0 
192.168.239.0/24 via 192.168.36.254 dev eth0 
192.168.36.0/23 via 192.168.36.254 dev eth0
169.254.0.0/16 dev eth0 scope link 
127.0.0.0/8 dev lo scope link 
default via 116.xx.xx.xx dev eth1