Lisa,
Not sure if your situation is quite the same one I have to deal with, but this sounds familiar. How do you have security set on the app itself, not just the services? I had a problem with users getting a challenge until I learned this:
In IIS Manager, go to the folder that contains the Flex app, disable anonymous authentication and enable Windows Authentication on the app. This will allow anyone on the network or domain to open the app, but users will get a message for each layer they are not allowed to see. They can dismiss the message box and still see any layers that might be open for everyone.
Hope this helps,
Jill Halchin
Southeast Archeological Center
National Park Service