I was talking to Chef: using the same, or similar, blue from SMB2 Mario's sprite in place of the brown in SMB1 Mario's wouldn't have clashed with the background color.
BUT... Maybe it just would've looked weird. Here's the palette NES games have to work with:

The more I think of it the more I think one of those deep blues or black in place of the brown actually wouldn't have looked so right in SMB1