Hmmm. I think you guys missed that this was a fellowship interview, not residency. Different rules apply to fellowship than residency, as there is no match and the programs can accept someone at any time. I guess my recommendation is to interview earlier, since if they like you enough they may offer you a spot before finishing the interview season, but every program is completely different, so it's difficult to say.