As well as considering colour - you should at least consider if you can make something more conspicuous by it's absence of colour - i.e. a black background, in which case be sure to use a larger clear font colour such as white for ensuring readability.
I think the notification bar here at StackExchange works well, which I think is white on black. If necessary you can incorporate branding and colour themes a little by making it a very dark version of a colour as the background.
Naturally, any notification colour scheme depends on how it contrasts with the rest of your colour scheme. A yellow notifaction is less suitable if the rest of the scheme is a similar colour, for example, but if the rest of your scheme is already black then this concept is less suitable and perhaps the yellow should indeed prevail.
Consider whether your colour schemes may vary across pages or other content. If you have quite varied content, especially with a lot of images, then picking a generic notification scheme that stands out in all situations is tricky, and this black background may complement more scenarios than other colours.
Ensure consistency as this will breed familiarity and therefore faster recognition, allowing notifications to be registered as such more quickly, but also bear in mind that users frequently ignore and dismiss notifications without reading, so really important notifications may need something extra that attracts the user's attention. One alternative to providing a dismiss capability is to show the notification for a specific time period, possibly fading it in and out smoothly.
Whatever the situation, use notifications sparingly as they are strong distractors - there are plenty of questions here on ux.se about notification best practices

