Neither apt nor yum (depending on whether your maintenance architecture uses .deb or .rpm files) suffers from dependency problems.

A given repository may not show a complete set of updates at a given time, which will cause either tool to reject the updates as incomplete (missing dependencies). This is not a problem - it's the correct decision! Once the repositories show a stable complete set of updates, they will be applied.

I've been running regular maintenance on many systems for many years, and have not experienced a problem. Understanding why maintenance updates are being rejected is the key.

There are some tools that can make incremental updates easier. for example, for yum there are a set of plugins:

yum install yum-fastestmirror yum-skip-broken yum-utils

You can then add the option '--ignore-broken' to your yum commands, and yum will try to apply as many dependency complete updates as possible (instead of giving up when encountering a missing dependency).

You can also periodically run:

package-cleanup --oldkernels --count=3

This will keep the latest three kernels, cleaning up the old ones (and dependent packages).

In short, the key to using apt or yum is regularly scheduled maintenance, and proper use of the included toolset. This causes small, incremental and easily managed changes to be applied to the systems. Trying to apply huge changesets, like a service pak, is where you will run into grief (and major system impact).