I can easily do one frame in photoshop, but does that mean I need to replace every frame or is there an easier way?
Yes, some things come the hard way. Whether you paint it frame by frame in Photoshop or animate a mask frame by frame in AE makes little difference - you still need to isolate the foreground objects somehow before being able to insert something in the background, whether that's a retouched version of the original, a photo or whatever. And I hope you are aware of the copyright issues involved here...
My suggestion would be to animate a mask for the duration of the shot, covering the sign. In Photoshop, create the replacement and import the picture into your comp. position it to fill the hole created by the mask and with some parenting, you should be fine?
Now, this is the first actual suggestion I am making, and there are probably much better ways to do it, but for someone with limited knowledge in all the products mentiond (me that is..) it is the best I have!
Hope it is helpful.
As Mylenium said, you need to isolate foreground and background objects - i.e. you need to rotoscope them. It's much easier to do with Mocha (which is included with AE).
You may start learning it here or there. Tutorials are downloadable, so if you have some troubles with watching those tutorials online (sometimes Imagineer's server is down), just dowload the files. Or simply google 'rotoscoping with mocha'.
And yes, do it for the sake of your skills improvement, bearing in mind copyright issues.