Why does Ubuntu require restart to complete updates?

What you read was true. Most administrators will brag about their machine's uptime. It could be days, months or even years.
However, what you need to know is, those machines are not your everyday Desktop Systems. They are specialized Server machines.

First thing about them, they rarely run X11. Most server systems will usually always be only on the Terminals. So, an upgrade on XServer doesn't matter.
Second, as Karthik pointed out, an update to X Server only requires that you restart X, not the whole machine. So your uptime still remains.

Another very important point is, Server systems don't update to the latest Kernel Version as it comes out. On Ubuntu, you are probably using version 3.2 right now. On my Arch System I am using version 3.6, but many of these systems boasting of long uptimes, are still probably somewhere in the 2.xx line, albeit completely secure with backported patches.

All updates on such systems are done only in-place. The updates are first tested on a testing machine, and after thorough testing to make sure nothing breaks, and that a reboot is not required to implement it, they are upgraded by the administrators.

You could do the same on your Ubuntu System too. But then forget about automated updates. Do a bit of testing and try and make your updates in-place. Even Kernels can be hot-swapped. However, it takes a lot of skill and expertise to pull it off successfully everytime.

This is the case ONLY if the linux kernel itself is updated. All other kinds of updates are applied directly. Kernel cannot be replaced while its running and thus needs a reboot.

A kernel update should happen rarely during regular updates and commonly done only during the upgrade cycles (12.04-12.10, etc)

You can choose to not restart, it will continue to use the old Kernel.

Edit: Kernel Hotswapping can be done to prevent the reboot in theory, but it doesnt look to be remotely trivial.