"could not find stored procedure"

Walk of shame:

The connection string was pointing at the live database. The error message was completely accurate - the stored procedure was only present in the dev DB. Thanks to all who provided excellent answers, and my apologies for wasting your time.

You may need to check who the actual owner of the stored procedure is. If it is a specific different user then that could be why you can't access it.