SQL Server 2000 SP 4 Issue With Query

This query executes (instantly) in SQL Server 2000 without SP4. With SP 4, it hangs - goes over 5 mins and does nothing. If we make the following change to the query: (replace the variables with actual values)
...
where Links.Matter_ID = 5872

AND Links.Entity_ID = 1

Order By Contacts.ContactID
...
It executes almost instantly in SP4 as well.
Looks like a SP4 issue, any ideas on how we could fix this?
t-sql follows:

Declare @MatterID bigint

Declare @EntityID int

Declare @ReturnDetails int

Declare @RETVAL VarChar(8000)

Declare @EntityDetails VarChar(1000)



Set @MatterID = 5875

Set @EntityID = 1

Set @ReturnDetails = 0

DECLARE Entity_Cursor CURSOR FOR

Select CASE WHEN Contacts.Job_Title IS Null Then '' Else Contacts.Job_Title + ' ' End + CASE WHEN Contacts.First_Name IS Null Then '' Else Contacts.First_Name + ' ' End + CASE WHEN Contacts.Middle_Name IS Null Then '' Else Contacts.Middle_Name + ' ' End



+ CASE WHEN Contacts.Last_Name IS Null Then '' Else Contacts.Last_Name End EntityDetails

From Links

INNER JOIN Contacts

On Links.Contact_ID = Contacts.ContactID

where Links.Matter_ID = @MatterID

AND Links.Entity_ID = @EntityID

Order By Contacts.ContactID



OPEN Entity_Cursor

FETCH NEXT FROM Entity_Cursor INTO @EntityDetails

Select @RETVAL = ''

WHILE @@FETCH_STATUS = 0

BEGIN

Print 'test'

/* If @ReturnDetails = 1

Select @RETVAL = @RETVAL + @EntityDetails + '
'

Else

Select @RETVAL = @RETVAL + @EntityDetails + ', '

FETCH NEXT FROM Entity_Cursor INTO @EntityDetails */

END



CLOSE Entity_Cursor

DEALLOCATE Entity_Cursor