By the rules, I can't recall anything that says out loud that you are supposed to roll a bluff check in that event, so (unless disproven, because proving negatives is impossible unless I read all the D&D 3.x material again) I'd say this is a case of the DM using his authority to ask for a roll.

Now, was what he asked fair?

Of course this is deep into the speculation zone, but I think it has a solid basis.

Since the rules tell nothing about rolling to disbelieve true things, your DM could have just said, "No, the NPC does not believe that you're telling the truth. In fact, he believes you're either lying in a very convincing way or you've been fooled into believing by someone else."

Diplomacy, bluff or charisma checks of any sort are useless to convince him you've not been fooled, unless you're known for not being gullible (and in that case, they're an automatic success).

Bluff is not really great even for convincing someone you're not lying: I would have asked for a diplomacy check instead. Truth is, bluff is often used to represent body language (I think it was used to relay messages to people not speaking your language, but that might just be my DM's ruling), so I see your DM's reasoning.

Were you better at diplomacy than bluff, I'd see a problem in your game. If not, he just gave you a (small) chance to luckily shine.

... the difficulty in proving a negative notwithstanding

RAW: yes, roll, usually

RAW has no problem with PCs using skills "on" other PCs (there's nothing in the Bluff Skill Description preventing it, for instance). Similarly, PCs would use Hide/Move Silent vs. Spot/Listen to hide from each other, just like PC/NPC interactions.

Note, however that Diplomacy specifically mentions that it's only usable on NPCs:

You can change the attitudes of others (nonplayer characters) with a successful Diplomacy check; see the Influencing NPC Attitudes sidebar, below, for basic DCs.

Don't be a Dick

I've had one game break up entirely (and a couple of others have rough patches) when one PC tried to lie to the rest of the party, but I've also had great fun in games where PCs were lying to each other; the latter were funny and good-spirited, while the former were potentially plot-relevant. YMMV†.

Thus, from personal experience, I would recommend role-playing the interaction, and erring on the side of not lying (at least, not about important things). Then roll, keeping in mind the Bluff/Sense Motive modifiers (and any situational modifiers that might be appropriate, if one character is a known fibber).

† Your Mileage May Vary