Bob,
You are correct. The original 18th century Winter Palace was cream and white with gilt ornamentation. When it was first built, remember that the General Staff Building, the Hermitage, the New Hermitage, etc. had not been constructed, and the Palace stood independantly.
The staff building was constructed by Rossi during the reigns of Alexander I and Nicholas I. The staff building was painted yellow and white (the scheme for all official government buildings in the Kremlin, even today).
By the time the staff building was complete, and the Winter Palace needed a paint job, Nicholas I declared that all residences of members of the Imperial family should be painted a dark red, which recalled early Muscovite palaces. As a result, for most of the nineteenth and through to the early 20th, the Winter Palace was painted a dark red with beige trim and gold.
After the revolution, the palace was repainted the lovely pale blue-green it is today. That color was taken from other buildings designed by Rastrelli, who preferred it -- the Stroganov palace is the same color.
In the mid-nineteenth century, the strong red and yellow buildings must have been quite something.
To read more about this, find a copy of Geraldine Norman's history of the Hermitage, which is teriffic.
Best, Nick