I was stuck with this problem near the end of an upgrade:

WARNING: this version of the GNU libc requires kernel version 2.6.24 or later. Please upgrade your kernel before installing glibc.

The installation of a 2.6 kernel could ask you to install a new libc first, this is NOT a bug, and should NOT be reported. In that case, please add lenny sources to your /etc/apt/sources.list and run: apt-get install -t lenny linux-image-2.6

Their suggested stepds dont work on VPS, and after googling, I came up to this: Why did my upgrade to 12.04 fail with "glibc not found" or "libc6" or "requires kernel 2.6.24" error?

There is comment by izx which explains my problem and proposes a workaround (might take a while to convince the guys to upgrade the kernel..).

However, when I follow his instructions, I get error:

# apt-get -f install
Reading package lists... Done
Building dependency tree
Reading state information... Done
Correcting dependencies... Done
The following extra packages will be installed:
  libc-dev-bin libc6 libc6-dev libnih1
Suggested packages:
  glibc-doc
The following packages will be upgraded:
  libc-dev-bin libc6 libc6-dev libnih1
4 upgraded, 0 newly installed, 0 to remove and 394 not upgraded.
1 not fully installed or removed.
Need to get 0 B/7737 kB of archives.
After this operation, 233 kB disk space will be freed.
Do you want to continue [Y/n]? y
locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.15' not found (required by locale)
locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.14' not found (required by locale)
Preconfiguring packages ...
(Reading database ... 35175 files and directories currently installed.)
Preparing to replace libc6-dev 2.13-20ubuntu5.2 (using .../libc6-dev_2.15-0ubuntu10.3_amd64.deb) ...
Unpacking replacement libc6-dev ...
Preparing to replace libc-dev-bin 2.13-20ubuntu5.2 (using .../libc-dev-bin_2.15-0ubuntu10.3_amd64.deb) ...
Unpacking replacement libc-dev-bin ...
Preparing to replace libc6 2.13-20ubuntu5.2 (using .../libc6_2.15-0ubuntu10.3_amd64.deb) ...
locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.15' not found (required by locale)
locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.14' not found (required by locale)
Checking for services that may need to be restarted...
Checking init scripts...
runlevel:/var/run/utmp: No such file or directory
Checking for services that may need to be restarted...
Checking init scripts...
runlevel:/var/run/utmp: No such file or directory
WARNING: init script for samba not found.
Stopping some services possibly affected by the upgrade (will be restarted later):
  cron: stopping...done.

WARNING: this version of the GNU libc requires kernel version
2.6.24 or later. Please upgrade your kernel before installing
glibc.

The installation of a 2.6 kernel _could_ ask you to install a new libc
first, this is NOT a bug, and should *NOT* be reported. In that case,
please add lenny sources to your /etc/apt/sources.list and run:
  apt-get install -t lenny linux-image-2.6
Then reboot into this new kernel, and proceed with your upgrade
dpkg: error processing /var/cache/apt/archives/libc6_2.15-0ubuntu10.3_amd64.deb (--unpack):
 subprocess new pre-installation script returned error exit status 1
Processing triggers for man-db ...
locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.15' not found (required by locale)
locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.14' not found (required by locale)
Errors were encountered while processing:
 /var/cache/apt/archives/libc6_2.15-0ubuntu10.3_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

I also attempted to manually grab the .deb package and install it using dpkg -i, but getting:

locale: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.15' not found (required by locale)

Even though the file is: libc-bin_2.15-0ubuntu10+openvz0_amd64.deb