I have a 61 key and don't find it a problem, but then other people used to larger keyboards do. Just make sure it has handy octave-transpose buttons and you can do a bit of quick transposing mid-song if you need it.
EDIT: several years on, I do find 61 keys restricting, and don't use the 61 anywhere near as much as 88 - that's mostly for live playing - the 61 is o.k. for recording, with its octave switch.
I also use an 88, except the top octave doesn't work. That's far less of a problem (to me) so a good compromise could be a 73-76.