Sounds similar to the problem I had with the custom notifications via handcent when I first installed it - turn off your 'stock' notifications completely and just use settings profile to set the notifications and see how that works out for ya
Ah right, cool, i'll give it a go and see what happens