I have run the OPs query against both SQL2000 and SQL2005 and received no errors. Sergiy is on to something though...
I used the following query:
SELECT
CONVERT(char(4), P.name) Name
,CONVERT(char(19), p.starttime ,121) StartTime
--> ,CONVERT(char(19), p.starttime ,121) pStartTime
--< ,p.starttime pstart
,CONVERT(char(19), s.starttime ,121) starttime
--> ,CONVERT(char(19), s.starttime ,121) sstarttime
--< ,s.starttime sstart
,CONVERT(char(19), s.endtime ,121) endtime
,p.errorcode
,p.errordescription
FROM MSDB..sysdtspackagelog P
INNER JOIN MSDB..sysdtssteplog S ON S.lineagefull = P.lineagefull
WHERE P.name LIKE 'MyDTS%'
AND P.lineagefull = 'MyGUID'
ORDER BY S.starttime
Note: Replace MyDTS and MyGUID with values from your DTS package log tables.
Interestingly, uncommenting either matched (--> or --< ) pair of comments allows the query to return the correctly ordered result set every time... (When uncommenting the --> comment the original starttime lines)
I don't exactly know what that means but the moral of the story is if you want correct results make sure there is no ambiguity in the result set column names/aliases.