Some remotes need programmed to work with whatever... sometimes that programming "goes away" and all the unit needs is reprogrammed -- unfortunately, you need the remote user's manual to locate the correct code/procedure to reprogram (this assumes your remote is this kind)
there is a web site (in California, I think) that sells remotes for various equipment -- my TV remote (Sony) died a slow death and the only way to "program" the TV to add/delete channels was with the remote -- they had one that did the job... you might do a search on "remote control" or something similar to see if you can locate that site (sorry, I didn't mark it)
of course, as technology goes, the VCR is so cheap anymore, a new VCR might be the cheap way to go....