Try connecting them when they are 6. Just because they are adults doesn't mean they are quite ready YET. Like in real life. And also like my virtual cat game on the computer, Catz 5 for all who are interested. On Catz 5 they turned into adult Catz today, but it took them over an hour for them to get used to one another and to get ready to mate. Tamagotchi seems to take longer to become fertile.
Btw I don't connect anymore. My friend gave me her Tamagotchi to modify and asked me to take out the infrared (the actual infrared, not just the window). So now it cannot connect anymore, it will always say, "Fail".