I also recently did an upgrade from 3.8 to 3.9, and using the syntax on the OpenBSD Upgrade Mini-FAQ
Code:
pkg_add -ui -F update -F updatedepends
worked for me. Maybe since you're telling it to upgrade packages for which no update information is available (since they were installed under 3.8 which had no update capability) it doesn't actually do the update unless you force it with the -F option.