Is there any documented case in which floating substances led to the introduction of a new species?
There is a number of reported cases of marine species reaching new locations through "hitchhiking" in recent times. However, it seems harder to find reports of species actually becoming established in a new location through this. 

The following articles describe examples of species transported with ocean debris:

In an early study on the dispersal of plastic pellets (3), it was suggested that pellets encrusted with the bryozoan Membranipora tuberculata was transported to New Zealand across the Tasman Sea from Australia. Barring one exception, this was the first time the species was observed in New Zealand waters.

Appendix A of a later article by the same author (1) contains 13 examples of species transported by sea (not necessarily through debris, or invasive), including the previous example. Of it, the author writes that


  Later, L. M. Stevens (1992, unpublished data) was to report that [Membranipora tuberculata]
  was abundant on both eastern and western shores around northernmost
  New Zealand.


Thus, this is possibly a case of a species transported on floating debris and subsequently becoming established in a new habitat.

Jose Derraik also deals with the topic in a review (4):


  Plastics floating at sea may acquire a fauna of various encrusting
  organisms such as bacteria, diatoms, algae, barnacles, hydroids and
  tunicates (Carpenter et al., 1972; Carpenter and Smith, 1972; Minchin,
  1996; Clark, 1997). The bryozoan Membranipora tuberculata, for
  instance, is believed to have crossed the Tasman Sea, from Australia
  to New Zealand, encrusted on plastic pellets (Gregory, 1978). The same
  species together with another bryozoan (Electra tenella) were found on
  plastics washed ashore on the Florida coast, USA, and they seem to be
  increasingtheir abundance in the region by driftingon plastic debris
  from the Caribbean area (Winston, 1982; Winston et al., 1997). Minchin
  (1996) also describes barnacles that crossed the North Atlantic Ocean
  attached to plastic debris. Drift plastics can therefore increase the
  range of certain marine organisms or introduce species into an
  environment where they were previously absent (Winston, 1982).


Finally, the book Marine Pollution: New Research (2) contains the following passage which ends with the observation that conclusive proof is difficult to obtain:


  Drift plastics are known to have introduced exotic marine species to
  several areas (Winston et al., 1997; Deraik, 2002). Winston et al.
  (1997) reported that the non-indegenous oyster Lopha cristagalli was
  fond on plastics wshed ashore in southern New Zealand, and that the
  exotic bryozoan Thalamoperella evelinae was found on plastics washed
  ashore in Florida. Barnes and Milnder (2005) fond the exotic barnacle
  Elminius modestus on plastic debris in the Shetland Islands (Atlantic
  Ocean). The bryozoaen Membranipora tuberculate is believed to have
  crossed the Tasman Sea from Australia to New Zealand rafting on
  plastic pellets (Gregory, 1978). M Tuberculate and the bryozan Electra
  tenella seem to be increasing their abundance on the Florida coast by
  drifting on plastic debris from the Caribbean sea (Winston, 1982
  Winston et al, 1997). Maso et al. (2003) (...) However, attributing a
  marine biological invasion to floating marine debris and not to other
  mechanisms is very difficult in most cases, and available data are
  generally insufficient.