There is another workaround, which is actually a bug I think, but mah...
- Suppose you want to underline in blue. Highlight something in blue.
- Right-click on what you just highlighted, and make it underlined instead.
- Select the underline tool.
- Do cmd-z twice. This will remove the underline you just did.
- Underline what you want: it will be underlined in blue! :)
Steps 2 and 3 are actually interchangeable.
Edit: I have actually better:
- Write any text with color 1.
- Change its color to color 2.
- Select the highlight or underline tool.
- Do cmd-z. This should change the text color back to color 1. (If it is not the case, make sure the text you have written is not selected.)
- You now have the underline/highlight tool selected with the color box accessible. Select your color (even if already selected), then highlight/underline.
This was my Preview bug finding day :) Enjoy!