Question: What level of complexity should a Use Case diagram illustrate - how much detail should be included, and what is the "cut-off" point for when a Sequence Diagram, or alternative UML diagram should be used?

Answer: 
Although the UML spec lets quite a lot of freedom as to what may appear in any UML diagram, the following should go into a UC diagram:

* Actors
* Use Cases
* possible a boundary that symbolizes the system under consideration (SUC).

This for the "main" UC diagrams, but you will likely create others that include requirements and/or classes of the design, etc.

Now, the actors are all objects that interact with the SUC in first place. Use cases are all those bubbles that signify some individual added value (not some technical procedure!!) the SUC offers to its actors.

Use case diagrams are about added value of the system, not about technical features!
The short answer, of course, is whatever level of detail (rather than complexity) is necessary. For the more thoughtful, use cases are most often used by the analyst to demonstrate to the non-technical stakeholders that all of their use-based requirements are being met. To that end, there should be enough detail so that managers, customers, and marketing have confidence that the developers will develop the product they want. For use case diagrams that capture decisions for developers, there should be enough detail that deeper design or programming can continue. It is best not to develop diagrams that try to address the needs of both types of users (stakeholders and developers). Finally, this is an iterative process of drawing and review. Start simple and add detail as necessary.