My computer started resetting itself randomly (sometimes after ten seconds, sometimes ten hours).

I'm told this is being caused by the power supply being insufficient for all the hardware i have installed (the graphics card epecialy apparently - Geforce 4 MX).

Is this correct? How much is it for a new power supply? Will an increased power supply potentially damage any hardware?

Any help would be greatly appreciated.

More than likely. I dont know what the best ATX PSU's around are, but you need to perhaps list exactly what devices and cards you have and then determine what sort of supply you need. Better to have too much available, than too little.
Hopefully someone else can recommend a decent PSU for your spec., so post what your running.

1.7 Ghz Athlon
256 Mb RAM
40Gb HDD
GeForce MX 440 (128Mb RAM)
Avance AC'97 Audio for VIA Audio Controller

DVD Rom
DVD RW

Board: Gigabyte Technology Co., Ltd. GA-7DXE 1.x
Bus Clock: 133 megahertz
BIOS: Award Software International, Inc. 6.00 PG 08/20/2002

Printer, Digital Camera and ADSL Modem running off USB (All the problems started with installing the USB ADSL modem - I think it tipped the PSU over the edge)

400watt to 450watt ought to take that lot in its stride. My trade supplier has just started listing 650watt PSUs !

I'm only a software nerd - hardware is alien territory to me - if I take it in to a shop to be upgraded how much am I looking to pay?

Take your old one out, take it to your local pc component supply shop (one that obviously has a good range and wont rip you off), show it to them, tell them you want a 400-450watt (as DJNafey said) replacment. Dont let them talk you into buying an 'ultra-quiet' one if your not that bothered about a bit of noise.
Alternatively, take out your PSU unit, measure it, look on sites like ebuyer etc, and get one of the net that again is 400-450watts. If your worried about installing it and taking it out, ask a nice friend who has done it before :-)

you can pay anything from £15.OO - 50.00 for a PSU, but obvioulsy for a long-life and reliabiltiy, you should aim towards the upper reaches

Yes, an ATX power supply shouldn't be difficult to remove. However, if you want to take it into a repair shop, expect to pay 1 hour's labour - probably about £25-£50, depending on where you go - the big shops have bigger overheads so they'll charge more than the bloke working on his own from his small office unit.