Newton's theory explained the changes in sea level by the effect of gravity (moon/sun). Now we are trying to detect gravitational waves from distant cosmic surces. But, apart from the differences in "signal frequency" (extremely small in case of sea effects (10-4 / 10-5 Hz or so), maybe higher in case of "signals" from cosmic sources (in the order of 1 Hz?) what is the difference in principle? At least in principle, can we say that the change in sea level is an effect of gravity waves?
There is a crucial difference between the Newtonian time-varying field effect and the long distance effect, in that the Newtonian effect is what is called "near field" and the radiative transmission of energy is by a "far field". It is the difference between an electrostatic force and a radio wave (Lubos Motl's answer gets at this, but it is possible to elaborate using electromagnetism as a direct analog. Gravity has more components, and is less intuitive, but it is the same idea).
Not all time-varying field responses are true waves. If you hold two charges, they have an electrostatic force. If you move one of the charges around the other, you get a time-varying electrostatic field on the other. This effect can lead to all sorts of oscillations on the second object.
But this time varying field is, when the objects are separated by less than the speed of light divided by the typical oscillation period, not an electromagnetic wave. It is just a time-varying electrostatic field.
The electrostatic field dies off as $1/r^2$, and so the energy density in the field dies off as $1/r^4$, which means that the total energy going past a sphere of radius R dies off as $1/R^2$. If there were radiation going out, the amount of energy going past concentric large spheres would be roughly constant, as the ratiation passed the spheres, and this requires fields which fall off like $1/r$, not $1/r^2$.
The difference in falloff of the two kinds of fields is important. There are proposals for near-field electrostatic and magnetostatic communication. In practice, this just means using a radio wavelength bigger than the distance between the objects, so that you would have them nearly touching, and then you can synchronize them with signals that are too small to be registered from far away (because static fields fall off much quicker than energy carrying waves).
The magnetic fields generated when you move an electric charge in a circle, together with the induced electric fields from the magnetic field, does only die off as $1/r$, meaning that the total energy density carried across larger and larger spheres is constant. This energy flux is the electromagnetic wave energy, and it is the far-field, or radiative field component of the electrostatic situation. The near and far field are not continuously related, they cross over, so that the far-field responses are not intuitive as compared to the near field.
Gravity also has a near-field $1/r^2$ force, and this is also carries negligible energy and has zero detection possibility at long distances. The induction of components other than time-time of the metric tensor is is required to have gravitational waves, and this is not possible in Newton's conception.
So it is not correct to say that Newton was considering gravitational waves, even when you make gravity propagate at finite speed, because the effects you are considering are all near field effects, while the true gravitational radiation is far-field.
The difference between observable effects of a variable/periodic gravitational field – e.g. tides – and gravitational waves is that
In contrast, the influence of gravity is immediate in Newton's theory, so the "signals" move by an infinite speed. Also, there are no real "waves" that would exist independently of the carriers in Newton's theory. So the tides on Earth may affect the orbital motion of the Moon; however, the total kinetic plus thermal energy of the Sun, the Earth, and the Moon is conserved even in the presence of tides.
That's not the case when there are gravitational waves. For example, the binary pulsar that led to the 1993 physics Nobel prize is emitting gravitational waves, and as a result, the frequency of orbiting in this binary system is changing with time (by an amount that exactly agrees with the prediction of general relativity). The binary pulsar is losing energy whether or not the gravitational waves that are emitted act on something else (via dies) or not.