It is nothing to do with UPS.
Users are cached on every site collection they visit but until they do, they aren't present on that site. That means that you'll need to check for the user and, if you don't find them, add them. Once they are added you can add them to a group.
http://sharepointcoding.wordpress.com/2009/01/06/adding-a-new-spuser-to-a-web/