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.
help us help you! If you post a question, make sure you include a CREATE TABLE... statement and INSERT INTO... statement into that table to give the volunteers here representative data. with your description of the problem, we can provide a tested, verifiable solution to your question! asking the question the right way gets you a tested answer the fastest way possible!