Yeah, just googling, it looks like multiple cores can help.
Also, make sure you get an OpenGL compatible card (yes, laptops now come with graphics cards -- you can always add a monitor later), because it looks like Photoshop is one of the earliest applications (makes sense when you think about it) to utilize GPU acceleration techniques.
EDIT: Yes, definitely upgrade the graphics card -- Nvidia are one of the leading manufacturers in the GPU acceleration business.