Query Performance Problems With Join On UDF-based Computed Column

We have a table with a couple of computed columns. The value of the computed column represents a foreign key reference into another table. We're seeing a major performance problem doing a query joining between the two tables with one of the columns, but not the other. In other words, this kind of query is very fast:

select * from TheTable A, FKeyTable B
where A.ComputedColumn1 = B.KeyColumn

but this one sends the CPU usage of SQL Server to 99% for a very long time:

select * from TheTable A, FKeyTable B
where A.ComputedColumn2 = B.KeyColumn

The main difference we can see that the computed column that causes problems is based on a UDF, and the other one isn't (but again, both are computed). When I look at the execution plan, the slow query shows a Nested Loop (Inner Join) with a "No Join Predicate" warning, with the estimated # of rows being 70 million (which correponds to the product of 1016 rows in TheTable and 69K rows in FKeyTable). The fast query doesn't have that warning, and shows 1016 rows (the # of rows in TheTable).

Does anyone know why the usage of a UDF would induce this horribly inefficient join behavior? Anything we can do to fix it?

This is SQL Server 2005 SP2, btw.