Problem
When starting an App-V application on a client, a popup is shown asking for credentials (username and password).
If the credentials are entered, the application still doesn’t start.

In the event log (application), events from source ‘Application Virtualization Client’ with event ID 5009, 3008, 3001 and 3037 are shown.
 

Cause
A Windows update on the SCCM Distribution Point, specifically the kb2868623 update.

Workaround
Configure the website on the SCCM Distribution Point to Anonymous Authentication.

Resolution
Uninstall the update from the SCCM Distribution Point and reboot the server.

I’ve encountered this issue on the following environment:
Client: Windows XP
App-V: 4.5
SCCM: 2007 R2
Server: Window Server 2008 R2 (with and without SP1)