Your orig.ico file probably contains multiple dimensions. They will also be stored in the output file. This means a dimension of 16x16 will be upscaled to 256x256 and that produces an ugly image. The 256x256 resolution is most likely the first dimension. You can see all the dimensions with the following command:
identify.exe orig.ico
With the command below you can get a specific dimension/image by specifying the index (starts at zero):
convert.exe orig.ico[0] -background #FFFFFFFFFFFF0101 -compose Copy ^
-gravity Center -scale 256x256! -depth 8 temp2.ico
If the 256x256 dimension is the last image you should set the index to -1:
convert.exe orig.ico[-1] -background #FFFFFFFFFFFF0101 -compose Copy ^
-gravity Center -scale 256x256! -depth 8 temp2.ico