What problem does cache coloring solve?
Both avoiding aliases and avoiding excessive cache conflicts are valid reasons for using page coloring. Requiring page coloring to avoid aliases is unpopular because it places a mandatory constraint on page allocation. In general, modern non-embedded processors do not require page coloring to avoid aliasing. 

Avoiding aliasing issues in hardware increases hardware complexity, so earlier processors (and perhaps some more recent embedded processors) chose to place the burden on software. Hardware can avoid aliasing issues in a cache with more index+offset bits than bits in the page offset by (for example):


checking alternate sets on a cache miss (as done by AMD's Athlon; when an alias was detected the block was moved to the current virtual index)
including the virtual address bits used for indexing L1 in a (tag) inclusive L2 (on an L1 miss and L2 hit, if the virtual address bits match the corresponding bits for the request, no action is necessary; if the bits do not match, the appropriate set to probe is known [whether the block is also in L1 could also be stored in the L2 tags to reduce coherence overhead, so some probes might be avoided])
using set prediction to guess the extra physical address bits used for indexing (a misprediction would be discovered after TLB access and corrected)
using reverse translation (physical to virtual) on a cache miss to find possible aliases (I think a PA-RISC implementation used reverse translation for coherence)


Using page coloring to reduce conflicts (for caches with simple modulo a power of two indexing) is less unpopular because the page coloring is not required for correctness. If a particular color becomes scarce, a page can be mis-colored with only a possible reduction in performance. This rationale for page coloring also means that the number of bits colored is less constrained. The (less practical) ideal may be to match all physical index bits for the last level cache with the corresponding virtual address bits, but even coloring just four bits can substantially reduce conflict issues.

It might be worth noting that coloring for alias avoidance need not match virtual address bits with physical address bits. As long as all potential aliases share the same virtual address bits used for indexing, alias issues are avoided. However, matching physical and virtual address bits may be convenient (and provide predictable conflict in physically addressed levels of cache).