Hmm...it works fine here using aptitude. We can Provide: hal-cups-utils in system-config-printer-udev but that doesn't make sense.
Maybe Breaks and Replaces hal-cups-utils instead of Conflicts? - Fabian