Paginated Report Error in the Service: data source was found but the credentials were incorrect

I finally figured out at least part of the "why" question myself after trying a bunch of different things.

It turns out it was indeed a permissions issue. The gateway account had read permissions but not permission to execute a stored procedure on the SQL server. I discovered this by swapping out the stored procedure with an equivalent text query in the Report Builder. This eliminated the problem for me.

Adding execute permission on the database for the gateway account did not resolve the issue. I will update if I ever figure out how to get it to work with a stored procedure instead of a text query. This part of the question remains unresolved.