I can't explain why the permissions would make such a drastic difference. Maybe it has to do with SQL Server getting a cache-miss when trying to find the objects? First it will look for the object as owned by the user and, if not found, will look for one owned by DBO.
There's a KB article discussing that there is a problem but it doesn't go into what the problem is.
http://support.microsoft.com/default.aspx?scid=kb;EN-US;q282416-Mike