I am encountering the same problem with ArcReader (just downloaded, over a year after initial post to this thread) and similar startup failure with ArcGIS Desktop.
Try the steps in this link http://resources.arcgis.com/content/kbase?fa=articleShow&d=34472. That seemed to do the trick for us.