Symptoms

When using groups to assign Process Rights (View/Admin/ViewParticipate), group members may still not be able to see data from that process. Which group members are unable to see data may vary over time.
 

Diagnoses

In older versions of K2 blackpearl (in this case, 4.5 with update 1290), when saving Process Rights to the database, K2 would "flatten" group membership. In other words, it would resolve all group members and write each of them to the Process Rights table. This could lead to inconsistent results being stored in terms of process rights.
In later versions of K2 blackpearl, the Identity Service was introduced, and process rights are no longer "flattened" in the database.
 

Resolution

There are several options available on the "AuthInit" string, used to configure the AD User Manager. In short, there are a few tweaks that can be made that sometimes improve accuracy and performance of saving process rights. This KB article shows the various options available in the AuthInit string: http://help.k2.com/kb000661
You can try modifying some of these options to see if it improves your situation. Generally, you should leave IgnoreUserGroups=False. ResolveNestedGroups will depend on whether you have nested AD groups you need to use. OnlyUseSecurityGroups will not resolve Distribution groups, which could improve speed significantly, depending on your AD setup. IgnoreForeignPrincipals only applies to multi-domain installs.