Firstly, can you try simplifying your SQL to:
SELECT count(*)
FROM history h
WHERE h.period = '0:00:15'
AND h.request = '1'
AND h.stepped = '1'
AND h.ts BETWEEN StartTime AND EndTime
AND ( (h.name = Tag1Name AND h.value = Tag1Cond)
OR (h.name = Tag2Name AND h.value = Tag2Cond));
Other than that, I can't see why you wouldn't get values for two dates in the same month -- unless your data only contained monthly entries, which I'm guessing isn't the case.
Could you post some sample data from the history table?
Tom
2010-08-16 19:21:14