opc.three (5/6/2013)
Are you rebuilding every index? Maintenance Plans do this.Consider using a tool that inspects the fragmentation levels and only rebuilds indexes that actually need it. Here is a good one: http://ola.hallengren.com/sql-server-index-and-statistics-maintenance.html
+1 vote for this.
To the OP ... try to implement Ola's solution and pick a date with few or no connections. It will be impossible to find a perfect time but at least, a night or day with very little activity.
The beauty of Ola's solution, is that it is "smart". It lets you tweak or customize the rebuild options and you can skip tables with less than 1k pages, or customize your own.
I have a 1.5TB database and the job only takes 55 minutes. Initial run was painfully slow though, almost 12 hrs, but after that, that's all it takes.