Mani I know you obfuscated the error, but i'll bet you an internet cookie that the procedure being called references a different database or different schema than what the procedure belongs to.

it sounds like ownership chaining is being broken to me.

for example, if dbo.myprocedure , which exists in the database [SandBox], references ANY OTHER database, the calling user will get the error you describe.the same can happen if it references a different schema, like [SandBox].Finance.Tablename instead of [SandBox].dbo.Tablename, but that's a little rarer to encounter in my experience; most places avoid multiple schemas.