The most recent version of Kopete (version 0.12.2) does support video.
Did you get it to support video through a NAT firewall (e.g. the Linux box has only an internal 192.168.x.x address, it's not connected directly to the Internet)?
The only way I managed to get MSN video working through NAT was on Windows 98.
(Lior Kaplan already gave the complete answer so I won't repeat it here).
Cheers,
--Amos
