We recently had the same issue in SQL2005 that did not go away after SP4... Once we upgraded to Cumulative update 3 for SP4 the error went away... So there is some fix in one of the cumulative updates after SP4 that fixes this error... For us the same proc that was throwing thousands of these errors is no longer throwing and we did not have to change the logic... The error was being thrown in queries updating/inserting into temp tables and we were about to open a case with Microsoft.

Otherwise we found another workaround that creating an outer transaction for most of the body of the proc where temp-tables were being created so that the statements modifying temp tables were in an outer transation also caused SQL not to throw the errors at the expense of having a large outer transaction.