I seem to be cursed.
My iPad had been jailbroken for a while, but then I restored the normal firmware. Since then the 3G didn't work anymore. It just said "No Service".
Today, I went to the Apple Store and got the iPad replaced, as the antenna seemed to be faulty, or so the service lady said. The new iPad worked fine with 3G until I got home and restored the old backup. Now it doesn't connect to 3G anymore.
So basically I got an iPad replaced for nothing.