Any ideas? Is there anywhere else that I should make policy adjustments?
Each application that you launch via the Task Scheduler, either through policy or on the local computer, has its own unique permission requirements. The BGINFO application is no different. I ran the BGINFO.EXE through a scheduled task and kept the interface visible to the user. The application popped up and counted down. Then, it errored, indicating that the user did not have permissions. Upon further review, the user did not have permission to store the new bitmap to the %WinDir% directory. I changed the directory (under Bitmap|Location menu) to the local users directory. When I reran the scheduled task, it worked just fine. I did not need any special user rights.
Taking this one step further, you might want to consider deploying this in another way. For example, you could repackage this as an MSI and deploy through Group Policy software distribution, which would run at an elevated privilege. You could also look into a solution like PolicyMaker Application Security. This solution will allow you to elevate privileges for just specified applications, such as BGINFO.EXE. PolicyMaker Standard Edition also provides an easy way for your to distribute the BGINFO.EXE file through a file transfer policy.