This is how I managed it:
The idea is to change the background of the textbox, wich is the one that includes the color for the underline, the background is the one that draws the line. The color is controlled by the "Tint" however if you just change the Tint from the the control directly you would change the tint for all the controls that use that background instance, i.e. all the TextViews Widgets in your app. If you only need to change the color on a single control, you need to clone the background drawable and modify it's tint. Mutate is the method that actually creates the new instance.
My example is part of a xamarin custom renderer, however it could just as simply apply to java, if you switch the method names to lowercase i think.
var background = YourTextView.Background.GetConstantState().NewDrawable();
background.Mutate();
background.SetTint(newLineColor.ToAndroid());
YourTextView.SetBackground(background);