A deep turquoise blue works wonderfully with chocolate if you're feeling brave. However, as long as you use it as an accent via accessories, etc, it should be very easy to change in the future for relatively little cost if you get tired of it, or don't like it.
An alternative is to use variations of the colours that you already have but vary the textures of the accessories to make a subtle but definite change; for example, mohair throws, suede/leather cushions, wooden vases, etc.