There are several issues:

1) "a query not using the cluster index. It is running a full scan."

A "full scan" (of the table) acually returns all data from the clustered index. So this index is used. You might refer to a scan operation where a seek is expected. But that's just guessing...

2) "It updates 1 record at a time,..."

This sounds like a c.u.r.s.o.r. *cough* being involved. With such a "RBAR"-scenario you'll never going to get the performance improved.

3) "... but it is taking about 3 seconds per record."

There is definitely something going wrong. A single row update must not take 3sec under "normal" conditions.

But to find the root cause might take a while since there are quite a few candidates involved: the query itself, network issues, locking / blocking, triggers,...

Once we know what you're trying to do (by looking at some code and sample data) we might be able to help you and improve the performance by magnitudes. So please help us help you by providing some ready to use sample data as described in the first link in my signature.