If, in the process of writing a script using Invoke-SQLcmd cmdlet from the SQL 2005/2008 shell you get “Could not find stored procedure” back, but you know what you are executing IS there, or it is not even a stored procedure, check the input. In my case the input T-SQL had quotes around it, which is what choked the command. Remove the quotes from the input string – the issue goes away.