Really, its not worth trying to use a 555 for anything, especially long delays. As suggested, have the 555 counting faster, and have it cascaded into a decade counter, or frequency divider.
dunno if this is something you want to consider, but many PICs have built in clocks...
p.s. - i assume you aren't trying to drive the relay directly from pin 3 of the 555...? Even though it can source alot of current, use a transistor and DON'T FORGET the feedback diode!