Routing blocks of IPs on a linux server

Hello,

I am renting a telehoused dedicated linux server (Redhat), and have
the need for a large number of IP addresses. Initially I was allocated
64 IPs, which I added with "ifconfig eth0:X IP up". This worked fine,
and I could connect out with my connection properly bound to the IP I
wanted.

A few months later, I needed more IP addresses. I requested an
additional 128 IPs, and my host said that they had been forwarded to
that machine, and all I need to do is add them locally to use them.

This new block of IPs was on a different range than the other one, and
I was given a different gateway for it.

I performed the same "ifconfig eth0:X IP up" operation, and all of the
IP addresses were listed correctly when running ifconfig. However, I
was unable to connect out on any of them. Specifically, in my code, my
attempts to connect() on a socket after calling bind() with one of
those IPs did not succeed.
I managed to get partial success by running "route add default gw
gateway-ip eth0:X" for each of the IPs. This gateway-ip was on the
same range as the new block.
Now, I could connect out on one of the new IPs. However, I soon
discovered that there was still a problem. Whenever I connect out on
one of the new IPs, it works, but the other new IPs stop working. The
same thing occurs if I attempt to ping from outside. The first one to
be pinged will reply, but subsequent ones in the new block do not.
It seems that after some period of time (maybe half an hour), the next
IP to be accessed will work.

I understand that there is probably a much better way of adding,
routing and using the new IPs than what I have done, but I lack the
knowledge on how to do this.

I am at my wit's end over this - I needed the new IPs to work six
months ago, and I am having huge problems because they don't.

Any feedback is greatly appreciated!
Thanks,
Chris