Bug 811549

This isn't a bug in SSSD. If you look at the error output you provided, you already have nss-util-3.13.3-3.fc16.x86_64 installed from updates-testing, which has a higher version than what is in fedora/fedora-updates right now.

You need to first do
yum downgrade "nss*"

And then you should be able to upgrade cleanly.

After downgrade I have that's versions:
# LANG=C rpm -qa 'nss*'
nss-3.13.3-1.fc16.x86_64
nss-softokn-freebl-3.13.3-1.fc16.i686
nss-softokn-freebl-3.13.3-1.fc16.x86_64
nss-util-3.13.3-2.1.fc16.x86_64
nss-myhostname-0.3-1.fc16.x86_64
nss-sysinit-3.13.3-1.fc16.x86_64
nss-softokn-3.13.3-1.fc16.x86_64
nss-tools-3.13.3-1.fc16.x86_64
nss_compat_ossl-0.9.6-2.fc15.x86_64
nss-softokn-debuginfo-3.13.3-1.fc16.x86_64

But update still not successful:
# LANG=C yum upgrade
Loaded plugins: auto-update-debuginfo, langpacks, presto, refresh-packagekit
Resolving Dependencies
--> Running transaction check
---> Package duplicity.x86_64 0:0.6.17-1.fc16 will be updated
---> Package duplicity.x86_64 0:0.6.18-1.fc16 will be an update
---> Package libipa_hbac.x86_64 0:1.8.1-9.fc16 will be updated
---> Package libipa_hbac.x86_64 0:1.8.2-10.fc16 will be an update
---> Package libv4l.x86_64 0:0.8.5-1.fc16 will be updated
---> Package libv4l.x86_64 0:0.8.7-1.fc16 will be an update
---> Package nss.x86_64 0:3.13.3-1.fc16 will be updated
---> Package nss.x86_64 0:3.13.4-2.fc16 will be an update
--> Processing Dependency: nss-util >= 3.13.4 for package: nss-3.13.4-2.fc16.x86_64
---> Package nss-softokn.x86_64 0:3.13.3-1.fc16 will be updated
---> Package nss-softokn.x86_64 0:3.13.4-1.fc16 will be an update
--> Processing Dependency: nss-util >= 3.13.4 for package: nss-softokn-3.13.4-1.fc16.x86_64
---> Package nss-softokn-debuginfo.x86_64 0:3.13.3-1.fc16 will be updated
---> Package nss-softokn-debuginfo.x86_64 0:3.13.4-1.fc16 will be an update
---> Package nss-softokn-freebl.i686 0:3.13.3-1.fc16 will be updated
---> Package nss-softokn-freebl.x86_64 0:3.13.3-1.fc16 will be updated
---> Package nss-softokn-freebl.i686 0:3.13.4-1.fc16 will be an update
---> Package nss-softokn-freebl.x86_64 0:3.13.4-1.fc16 will be an update
---> Package nss-sysinit.x86_64 0:3.13.3-1.fc16 will be updated
---> Package nss-sysinit.x86_64 0:3.13.4-2.fc16 will be an update
---> Package nss-tools.x86_64 0:3.13.3-1.fc16 will be updated
---> Package nss-tools.x86_64 0:3.13.4-2.fc16 will be an update
---> Package phoronix-test-suite.noarch 0:3.6.1-1.fc16 will be updated
---> Package phoronix-test-suite.noarch 0:3.8.0-1.fc16 will be an update
---> Package pyrpkg.noarch 0:1.15-1.fc16 will be updated
---> Package pyrpkg.noarch 0:1.17-1.fc16 will be an update
---> Package sssd.x86_64 0:1.8.1-9.fc16 will be updated
---> Package sssd.x86_64 0:1.8.2-10.fc16 will be an update
---> Package sssd-client.x86_64 0:1.8.1-9.fc16 will be updated
---> Package sssd-client.x86_64 0:1.8.2-10.fc16 will be an update
--> Finished Dependency Resolution
Error: Package: nss-3.13.4-2.fc16.x86_64 (updates-testing)
           Requires: nss-util >= 3.13.4
           Installed: nss-util-3.13.3-2.1.fc16.x86_64 (@updates)
               nss-util = 3.13.3-2.1.fc16
           Available: nss-util-3.12.10-1.fc16.i686 (fedora)
               nss-util = 3.12.10-1.fc16
Error: Package: nss-softokn-3.13.4-1.fc16.x86_64 (updates-testing)
           Requires: nss-util >= 3.13.4
           Installed: nss-util-3.13.3-2.1.fc16.x86_64 (@updates)
               nss-util = 3.13.3-2.1.fc16
           Available: nss-util-3.12.10-1.fc16.i686 (fedora)
               nss-util = 3.12.10-1.fc16
 You could try using --skip-broken to work around the problem
 You could try running: rpm -Va --nofiles --nodigest

This is still not an SSSD bug. Reassigning to nss.

In the first attempt it looks like the mirror chosen is not in synch per the
'nss-util-3.12.10-1.fc16.i686' being what's available and is older that what you have. Downgrading nss did not help 
.....
           Available: nss-util-3.12.10-1.fc16.i686 (fedora)
....

Again an older version available. This is not a problem of nss perse. I had a somewhat related problems before, see Bug 527867 and Bug 596840. Based on Bill Nottigham's advise and http://www.rpm.org/wiki/PackagerDocs/ArchDependencies I added the %{_isa} suffix. In another occasion this caused some other problems ,which I need to search for, so let's proceed with caution. 
I'll make this change to start with:
-Requires:         nss-util >= %{nss_util_version}
+Requires:         nss-util%{_isa} >= %{nss_util_version}
and let's do some testing in Rawhide and with some f16 scratch builds.

(In reply to comment #4) This may not be necessary after all. It turns out that the nss-util build was not added to the Bodhi update for some odd reason it's now added. The push will be fixed soon.

See https://admin.fedoraproject.org/updates/FEDORA-2012-5086/nss-util-3.13.4-2.fc16,nss-3.13.4-2.fc16,nss-softokn-3.13.4-1.fc16,nspr-4.9-2.fc16
which I have submitted to stable. Give it a day or two to show up.

Thank you. It seams fixed.

Why NOTABUG instead of CURRENTRELEASE??

I wasn't sure myself and chose NOTABUG because it wasn't a bug in nss perse but but a missing package in the bodhi push. On the other hand, messing up the Bodhi push causes problems to the user so it's is a bug after all so CURRENTRELEASE is more appropriate. Thanks.