Why Would Adding Dbo. Cause My Function To Run Forever?

Lately I did a mass update on all our scripts and added
dbo. in front of all tables and other objects.

There is a function that returns a table and the function is
I think 300 lines. There are a lot of UNIONs, EXISTS,
NOT EXISTS, etc...

Anyhow there's a single place where if i add dbo. in front
of the table this function which is being called from an SP,
when i run the SP from the QA or from the ASP application
it runs forever. As soon as i remove the dbo. again it runs
in 6-8 seconds. Here's the thing this same table reference exists
a few lines below in the 2nd UNION for example and
having a dbo. in front doesn't cause any problems.

Even more confusing if i add Databasename.dbo.TableName
and run it again, i don't run into any problem.
So it's almost like if i specify dbo. in front of the table, somehow
SQL Server or our code is getting lost and searching for this
table in other databases?

Has anyone run or seen such a problem?

I am sure I can make changes to the code and end up
writing a different code but before I make changes I would
like to find out more about my mystery problem.

I am running SQL 2000 SP4 and the same problem occured
on two different machines. Win 2000 Pro and Win 2000 Server.

Any ideas, suggestions?

Thank you