I had tried that right away and I got an error. But I tried it again later in the day and it worked. After the weekend, I can see all of the new fields in the formula field-picker as well.
So, I think I may have been moving too fast, creating new fields and expecting them to be instantly available in the formula builder drop downs. (I guess I would expect them to be, but there was a lag for some reason.)
Additionally, I think the error I was getting was because of a syntax error in a very complex CASE formula. When it worked later in the day, I had rebuilt my formula and double checked that everything was correct and I pasted in the new field Ids.
Thanks for the suggestion