Traceability should introduce no friction to the development process, particularly if it is to win over agilists. Focusing on task-based and test-driven development, continuous integration, single-piece flow, and single-source information with a minimum of intermediate artifacts can make it easier to use with many tools.
Combining basic version-control tool integration with build & test automation (with event logging, notification, and subscription) can automatically log and track tracing information from these activities, which can then be readily queried or scripted to produce necessary traceability reports.
A simple wiki-mechanism (such as Trac, FIT, FitNesse), to define and organize project terms/concepts, use-cases or requests, and related project content can go a long way toward achieving single-sourcing of information with appropriate linkages for subsequent querying & reporting. Use of readily available search-engines on an existing project's knowledgebase (project wikis, blogs, mail-lists, code, specs, docs, tests, models, etc.), along with consistent use of a project's terminology, can fill in many of the blanks for tracing across the lifecycle and its artifacts.
Promising approaches, such as event-based traceability, along with more sophisticated information-retrieval methods, can help automate this and, indeed, have been implemented in several tools, thus raising the bar for the industry in this area.