Complementary colors
Pyth, 9 8 bytes
Thanks to @isaacg for -1 byte!
sXz.HM16

Subtracting a certain color's value from 255 is equivalent to subtracting each of its hexadecimal digits from 15. Say a number is 16a+b. Then the value of the number created by subtracting its digits from 15 is 16(15-a) + (15-b) = 255 - (16a+b).
sXz.HM16     implicit: z=input()
      16      
   .HM        map hex representation over range
   .HM16     '0123456789abcdef'
  z           the input string
 X            Translate characters in x1 present in x2 to reversed x2
              that is, '0' becomes f, '1' becomes 'e', and so on.
              The initial '#' is unchanged.
s             That produced a list, so join into a string by reducing +

Try it here. Test suite.