...could they have lied about replacing it? It's such a cheap item, I'd replace it again. With the bucking stopping when your tank is full, I have to defer to the more experienced gang here.
Hope it works out for you, I know this takes away from that new car giddy feeling...but it should be resolved pretty soon I'd think.