You could use a Query List action to design a CAML query that checks to see if there were any items in the calendar match your criteria.
I created a simple workflow that ran on a list item that had 2 date fields - a start and an end date. My workflow checks the Calendar list to see if any items overlap with this date range. I'll admit I copied the actual CAML query from here: http://iguanagears.blogspot.com/2008/09/moss-caml-getting-month-and-date.html, it seems to work as advertised :)
In the Query List action, switch to CAML editor mode and use the following CAML. A couple of notes:
1) {8393F8A6-AEB1-4C30-AEF4-61E3CFF12ABE} is the ID of my 'Calendar' list.
2) {WorkflowVariable:StartCheckISO} and {WorkflowVariable:EndCheckISO} are two text workflow variables. CAML expects the dates to be provided in a particular format, so before the Query List action I have two 'Calculate a Date' actions, that take the date we are querying for from the 'current item', and store it as an ISO 8601 Date string into the text variable, which can then be used in the CAML query.
<Query>
<Lists>
<List ID="{8393F8A6-AEB1-4C30-AEF4-61E3CFF12ABE}" />
</Lists>
<ViewFields>
<FieldRef Name="ID" />
</ViewFields>
<Where>
<Or>
<Or>
<And>
<Leq>
<FieldRef Name="EventDate" />
<Value Type="DateTime">{WorkflowVariable:StartCheckISO}</Value>
</Leq>
<Geq>
<FieldRef Name="EndDate" />
<Value Type="DateTime">{WorkflowVariable:StartCheckISO}</Value>
</Geq>
</And>
<And>
<Geq>
<FieldRef Name="EventDate" />
<Value Type="StartTime">{WorkflowVariable:StartCheckISO}</Value>
</Geq>
<Leq>
<FieldRef Name="EndDate" />
<Value Type="DateTime">{WorkflowVariable:EndCheckISO}</Value>
</Leq>
</And>
</Or>"
<And>
<Leq>
<FieldRef Name="EventDate" />
<Value Type="DateTime">{WorkflowVariable:EndCheckISO}</Value>
</Leq>
<Geq>
<FieldRef Name="EndDate" />
<Value Type="DateTime">{WorkflowVariable:EndCheckISO}</Value>
</Geq>
</And>
</Or>
</Where>
</Query>
I store the results into a collection variable, and can then easily check the Count of the collection to see if there were any matches (using a Collection operation) action.
I hope this gives you some ideas
regards,
James