The crucial point with the conversion error can be demonstrated by trying these statements
SELECT 1 UNION SELECT 'A'
and
SELECT 'A' UNION SELECT 1
In both cases, you'll get
Syntax error converting the varchar value 'A' to a column of data type int.
And you'll get the error whether it's SS 2000 or SS 2005.
The reason lies in the description of the UNION statement and the rules for data type precedence.
The following extracts are from SS2000 BOL but the wording in SS 2005 BOL is very similar.
For the UNION statement,
When different data types are combined in a UNION operation, they are converted using the rules of data type precedence.
For the rules of data type precedence,
When two expressions of different data types are combined by an operator, the data type precedence rules specify which data type is converted to the other. The data type with the lower precedence is converted to the data type with the higher precedence. If the conversion is not a supported implicit conversion, an error is returned. When both operand expressions have the same data type, the result of the operation has that data type.
This is the precedence order for the Microsoft® SQL Server™ 2000 data types:
sql_variant (highest)
...
int
...
char
varbinary
binary (lowest)
So the order of the UNION's doesn't matter. It's the precedence of the data types that counts.
So we have an explanation for the error reported with SS 2005 (and 2008?).
But one puzzle remains.
Why doesn't the error occur when the query in the original question is run on SS 2000?