I had a similar problem (Gutsy/AMD64, 2.6.22-14-generic, kvm 1:16-1ubuntu2), in that tap0 wasn't visible (ifconfig -a) on my host, and kvm reported "can't add tap0 to bridge eth1: Operation not supported" when starting.
However, after my host finished booting and everything network related had finished initializing, tap0 had appeared, and I can configure them both to communicate without issue.
I had a similar problem (Gutsy/AMD64, 2.6.22-14-generic, kvm 1:16-1ubuntu2), in that tap0 wasn't visible (ifconfig -a) on my host, and kvm reported "can't add tap0 to bridge eth1: Operation not supported" when starting.
However, after my host finished booting and everything network related had finished initializing, tap0 had appeared, and I can configure them both to communicate without issue.