Like everyone else has said, I guess it depends on the program, but I copied/pasted two fellowships, one cardio and one child psych, where USLME step 3 is required. You can find a whole bunch more with the same requirements by Googling 'xxxxx fellowship'.
Which program did you apply for wanna_be_do? Did you hear good things back? The docs I work that didn't have USLME step 3s did the same thing you did, put COMLEX for USLME, but they weren't asked for an interview. Maybe they just plain sucked as applicants but...the programs specifically asked for USLME so it's a good bet that had something to do with it. As the links say, you can be a DO for those particular programs, they metion that's OK, but you need either "ECFMG Certification or USMLE Scores". I don't think they are accidently omitting COMLEX if they mention DOs. Right?
Look, I'm not trying to act like I know anything. I'm not a doctor, I'm not even in medical school yet, and wanna_be_dobut would seem to know about the process best because he/she has gone through it. But, I can read requirements posted online. They seem to be pretty straightforward, and I'm just trying to help a fellow student out