Wow, that would be quite a job to re-dye felt. I wouldn't even know how to go about doing it.
I did spray paint a campaign hat black for a costume, but it was disposable, so I wasn't too concerned about ruining it.
The important thing is finding the right color dye. Definietely contact a hatter to see what the process is.