An orthogonal coloring of the two-dimensional unit sphere S-2, is a partition of S-2 into parts such that no part contains a pair of orthogonal points: that is, a pair of points at spherical distance pi/2 apart. It is a well-known result that an orthogonal coloring of S-2 requires at least four parts, and orthogonal colorings with exactly four parts can easily be constructed from a regular octahedron centered at the origin. An intriguing question is whether or not every orthogonal 4-coloring of S-2 is such an octahedral coloring. In this paper, we address this question and show that if every color class has a non-empty interior, then the coloring is octahedral. Some related results are also given.