Typically the problem areas would be in versioning of dependencies (in particular, resolving conflicting version requirements for different packages, where dependencies form a DAG rather than a tree) or around install hooks (where installation / removal can't be represented simply by existence / absence of whole files on the filesystem).