I recommend getting at least these items (in order of importance):
CPU: I recommend a dual-core processor like the Intel Core 2 Duo which has improved multitasking and can encode video in less time. A Core Duo CPU is a little cheaper, but also less powerful. If your budget is really tight, an AMD Turion X2 is another option. Single-core CPUs are only if you are strapped for cash or really need a long battery life. I'd avoid Intel's Celeron or Pentium CPUs (single or dual-core), they aren't worth the performance trade-off unless you are really
in need of cash.
RAM: 1GB minimum, more is recommended. Video editing is very RAM intensive.
Video: Integrated graphics should be OK, but if you can find one with discrete graphics with its own dedicated memory in your price range I'd go for that since it won't use (as much) main memory for video RAM. Discrete graphics do have a downside in that they can use more battery power compared to integrated stuff.
LCD: 14" or 15" is preferred, larger LCDs suck a lot of battery power. 13" may be a bit small, so I'd try viewing one first. The trade-off may be a bit longer battery life, though.
DVD Drive: This should be a must. Get a DVD-/+RW, speed shouldn't matter much.
As for everything else, especially since you mentioned HDD size isn't important, I won't list any recommendations unless you have other specific needs (built-in mic or camera for chat, TV out, etc.) and wireless LAN should be standard.
For notebooks you can walk into a store and buy:
This HP model is a bit pricey: HP Pavilion dv6207TX
Compaqs are cheaper, but use AMD Turions: Compaq Presario V3230AU
Toshibas are also pricey: Toshiba Satellite A100/400
for a 15" LCD, Toshiba Satellite M100/600
for a 14" LCD.
For a Dell:
The $1699 AUD Dell is better, but the $1399 one is not bad, especially if you prefer WinXP: Dell Inspiron 6400
Hopefully, this helps you a bit.