For SQL Server 2005 and SQL Server 2008 the following solution will work.
In this solution the GROUP BY is replaced by PARTITION BY since you don't need GROUP BY aggregates like SUM or AVG, only ROW_COUNT.
CTE is being used, but you can implement it as subselect (derived table) also.
;WITH cteStaff AS
SELECT EmployeeID, DepartmentID, Counter=ROW_NUMBER()
OVER(PARTITION BY DepartmentID order by EmployeeID)
UPDATE e SET e.Counter = e1.Counter
FROM Employee e
INNER JOIN cteStaff e1
ON e.EmployeeID = e1.EmployeeID
Kalman Toth, SQL Server 2008 Training