Use tone-on-tone
When challenged by a color palette that restricts your options try different saturation levels of the same basic color to do the basic design, and then you can use heavy saturation of the color to draw the user's eye in to elements like status messages etc.
Use a color wheel
Remember your design friend the color wheel. Choosing highlight colors from say an analagous or triadic point on the wheel might give you the level of visual impact you need, and again play with the saturation levels to play off contrast.
Keep the basic design reasonably neutral
Some of the most effective sites I've created have been based off neutral palettes where I then used the brand identity colors for highlights. Its really good when someone says "I don't like that color" and you say "But its the official brand color"....
Don't forget other design techniques
From Jon W's answer to this question...
The use of Contrast and Sizing is
equally important. Call-to-action
buttons, alerts etc can be styled to
provide greater contrast against the
main content, or can be sized so that
they are more noticeable as well.
Totally agree with Jon W's answer. I would add to that change in shape as well, particularly on mouse events like hover.
