I'm handling nearly that may clients (between 900 and 1000) w/ a single WSUS server with no problems (on an underpowered old box, too). I don't think your problems are going to come from the WSUS server side.
Bandwidth to get updates deployed in an expedited fashion is going to be your biggest concern (especially if by "All locations connect to us over a T1 circuit" you mean that your head-office has only a T1 to the MPLS cloud).
If you have some locations with larger concentrations of client computers than others I'd consider deploying a replica WSUS server into those locations to cut down on duplicate update traffic crossing the wire. You're going to have to expend Windows Server licenses to deploy those replicas, but it may be worth the cost re: WAN bandwidth usage and expedited update deployment. It looks like WSUS can be hosted from a machine running the "Windows Web Server 2008 R2" edition of Windows, so you should be able to get by w/ cheap licensing (obviously, try it in a VM and see before you commit to spending money).