Does anybody know how I would change the colors of brushes? Like this:
http://www.youtube.com/watch?v=cgrjCME93as

Edited the title to have any information content whatsoever. -Hober

You would have to either download one of ians' maps in the COLOURS series and ask him for permission to use his textures, or make you're own. There's a bunch of great tutorials on using custom textures here.

Cant one just change the FX Color (R G B)?
(if its a func_brush)

I like how you link to a video explaining how he does this, and then ask how he does it.