You may require a BIOS update to handle x2, do some research and see if others have reported issues. Your board will take any socket 939 chip, and these are all priced very nice right now. I run a Toledo 4800 X2 and it rocks.
Any Athlon x2 will kick the pants off your 3500, you will be amazed at the difference when you are doing some heavy task and trying to multitask too.
Also suggest looking into the Opterons, I think they get a lot of praise for their value vs performance. Although if you don't OC, it might not make much difference. If you do a lot of video work, extra L2 cache (2x1MB) is a good choice.