The second gscatter syntax in your question looks correct,
gscatter(score(:,1),score(:,2),grp,[0.4940 0.1840 0.5560;1 0 0;0 0.8 0],'*',6)
It's not clear what you mean by "[it gives] me the colors I needed but not always in the right spot". The (x,y) scatter coordinates should always be the same.
The first gscatter syntax in your question is incorrect. The 4th input should indicate color, not symbol.
"Every time I run the code, grp doesn't always start with the same observation so the group number changes so I cant assign the color based on the group number"
Perhaps you mean that the color of the groups differ between iterations. If so, is that really a problem? If you're construction the legend correctly, the colors should always pair correctly with the legend strings.
If you'd like certain colors to be associated with certain groups (ie, "noise" is always purple) you'll need some way or identifying which group represents "noise". The kmeans algorithm doesn't have any idea what your data mean. It only partitions the data into groups. If you know that one group should always have a center that is below and to the left of other groups, you could use the 2nd output of kmeans() which idicates the group center points. Then associate the group values to each center point.
Alternatively, you might be able to pre-define the approximate center points of the clusters if you know them ahead of time using the start property of kmeans.