If things are backlit, shadowed, or the light is flat, it's easy to get the colour wrong, quite apart from the existence of colour variants in the species. I find degree of notching to be unreliable as a primary criterion. So I agree that these features aren't the most diagnostic.
However, the Sibley Field Guide to Birds of Western N. America (2003) says about European starlings "Distinguished from all other birds by shape and habits." The same guide also says that adult purple martin males can be confused with European starlings, which seems contradictory. However, I think the Sibley statement about European starlings is right, and the one about purple martins is wrong. Starling and martin shapes are so different that I can't imagine any circumstance in which they could be confused flying, perching, or walking. Perhaps I lack imagination.