Hi,
I had the same problem and I figured out, that adding someone to your contact list in kopete does not add the one to your ICQ-server-contact-list. But as long as the one you want to talk to is not on your server-contact-list you won't be able to see his/her online status or receive messages from him/her.
Solution: Use the ICQ-Webclient
go.icq.com and re-add the user to your contact-list. As soon as the user appears there you will also be able to see his/hers online status within Kopete.
HTH
Thomas