The potential challenges of threading in computer science include handling concurrency issues (race conditions and deadlocks), thread-safe data structures' complexity, overhead of creating and managing threads, and ensuring performance efficiency with multi-threading on multi-core processors.