The permissions granted to user are insufficient for performing this operation. (rsAccessDenied)

With my SharePoint 2010 launch looming, I rolled my site out to some "select" users to give the site some gas, revv up the engines, and hopefully not have it come to a screeching halt.  Almost immediately, my users encountered an unusual error when attempting to execute an SSRS report we converted - "The permissions granted to user <user> are insufficient for performing this operation. (rsAccessDenied)"

When I hit the site, everything worked fine for me.. then again... Im an "owner" throughout my site... so that doesn't prove much.  I also saw that I'm inheriting permissions from the parent site, where all domain users have read access.. so the user can see the report, they just can't execute it.  I spent a few hours looking at database permissions, SSRS report properties, etc.  In the end, I mistakenly uncovered the solution.

My SharePoint site has publishing features enabled, which is kind of nice.. but some things are treated as "private" until their approved.  With reports, that means data connections.  In my site, I wound up in my Data Connections Library (which should be visible after clicking Site Actions -> View All Site Content).  Within my data connection library, the approval status on my data connection read as "Pending"

Once I edited the data connection (hover over the name, expand the drop down that appears, and click Approve/Reject), and set the connection to Approved, all was right with the world once again.  Odd issue.. but happy in the end it was such a simple solution