This rather touches on how any one writer, show, etc decides to treat the effects of time travel. The process here seems to be that a change made in the past doesn't "happen", or manifest in the future until the person in question makes them.
Consider the bootstrap paradox - a person goes back to see who discovered the wheel, only to find that HE did, offering some caveman the idea to observe a tree rolling down a hill. In that case, the event (wheel) was already in place before he left, though he wasn't aware he had any connection to it.
Now consider the Predestination Paradox from Somewhere in Time. Christopher Reeve finds the guest book for the hotel from decades past, sees his name and signature in it, so he KNOWS he will succeed at traveling back in time. If the newspaper ads was already in existence before the Splinter machine sends the traveler back, they'd already know something went awry.
This appears to be a different situation - the newspaper ad only exists AFTER the person not only goes back, but actually places the ad. Now, logically, since the event still happens in the past, the ad should exist instantaneously upon their departure. I'm betting we're looking at a version of the grandfather paradox - if the ad appeared instantaneously, they could go back and get the subject immediately, BEFORE they placed the ad, or even sort out what went wrong before they left so it wouldn't. But they they wouldn't PLACE the ad, so the people in the future wouldn't be able to read it.
So same question - why doesn't it appear immediately? Best guess is in this version of time travel, there's a connection between the "present" and the person who goes back. if a person goes back and placed the ad two days after arrival, the ad would only appear two days after they left in the "present". There's a certain logic to that - something to do with Quantum, I expect...