Try gProject from the rgeos package:

library("rgdal")
library("rgeos")

# read shapefile and transfrom to UTM zone 36N (distances in m)
route <- spTransform(readOGR(".", "Trips"), CRS("+init=epsg:32636"))
stops <- spTransform(readOGR(".", "Stops"), CRS("+init=epsg:32636"))

l <- subset(route, route_id==1137)
p <- subset(stops, grepl("^1137_", UID))

plot(l, axes=TRUE, col="orange")
plot(p, add=TRUE, pch=19, cex=0.1)
text(p)

# distance along route
d <- sort(gProject(l, p))
d
# [1]     0  3051  3057  7221 10379 15657 20326 20326 22141 24262

# distance between stops
diff(d)
#[1] 3050.9166    5.9720 4164.2480 3157.7702 5278.5812 4668.1810    0.5878
#[8] 1814.9612 2120.8470