Faits: A. La parcelle n° 404 de la commune de A._ appartient depuis 1929 à la Société Y._. Les époux X._ sont copropriétaires de la parcelle voisine n° 682 depuis le 26 février 2003. Une villa y est érigée. B. B.a En 1931, les parcelles étaient configurées de manière différente et un chemin vicinal traversait certaines d'entre elles. A cette époque, un droit de passage grevant plusieurs fonds, dont celui portant aujourd'hui le n° 404, a été inscrit au registre foncier sous référence xxxx au profit de l'actuelle parcelle n° 682. L'acte constitutif de cette servitude mentionnait que « le droit de passage ne pourra être exercé que sur les parties desdites parcelles formant actuellement le chemin. » En 1951, ce chemin (actuellement chemin B._) est devenu une parcelle distincte et dépendante des parcelles riveraines et a été immatriculé au registre foncier sous n° 629. B.b Jusqu'en avril 2008, les époux X._, comme les précédents propriétaires, accédaient à leur terrain en empruntant un chemin privatif aménagé au début des années 1940 et traversant d'est en ouest la parcelle contiguë n° 404. Le terrain étant légèrement en pente à cet endroit, l'aménagement de ce chemin a nécessité l'élévation d'une petite bordure haute de 50 cm, longue de 8 mètres environ et large de 20 cm. De l'autre côté du chemin, en contrebas, un mur de soutènement de moins de 1 mètre de hauteur a été édifié pour retenir la terre et les éboulements. Les époux X._ disposent d'un autre accès à leur propriété, par son côté nord en suivant le chemin B._ qui contourne la parcelle n° 404. Cette voie permet le passage des véhicules à moteur. C. Depuis 2003, un litige oppose les époux X._ et la Société Y._ au sujet du chemin privatif que les premiers utilisent pour accéder à leur parcelle. Dans le cadre d'une action négatoire ouverte par les époux X._ contre la Société Y._, le Tribunal de première instance de Genève a, le 27 septembre 2007, rejeté la conclusion des époux tendant à ce qu'il soit constaté que la parcelle n° 404 est grevée d'une servitude foncière de passage au profit de la parcelle n° 682 s'exerçant sur le chemin traversant perpendiculairement (soit d'est en ouest) la parcelle n° 404. Il a également rejeté la demande reconventionnelle de la Société Y._ qui tendait à la constatation que les époux X._ n'étaient pas au bénéfice d'un droit de passage de nature réelle sur la parcelle n° 404. En bref, cette autorité a considéré que l'assiette de la servitude de passage ne correspondait pas au chemin qui traversait d'est en ouest la parcelle n° 404 mais au tracé de l'actuel chemin B._. Ce jugement est définitif et exécutoire. D. Après avoir averti les époux X._ que le passage traversant la parcelle n° 404 d'est en ouest allait être renaturalisé, la Société Y._ a entrepris, le 2 avril 2008, des travaux consistant à enlever le pavement de ce chemin et à y planter un arbre, empêchant ainsi l'accès à la parcelle n° 682 par cette voie. Les époux X._ ont ouvert contre la Société Y._ une requête de mesures provisionnelles urgentes tendant à ce qu'il soit fait interdiction de modifier, détruire ou renaturaliser le passage en question, à ce qu'il lui soit ordonné de le remettre en état afin qu'ils puissent à nouveau accéder à la voie publique, ces mesures devant être prononcées sous la menace des sanctions prévues à l'art. 292 CP. Par ordonnance du 13 mai 2008, le Tribunal de première instance a rejeté cette requête. La Cour de justice du canton de Genève a, le 25 septembre 2008, rejeté le recours formé par les époux X._ contre cette ordonnance. E. Par mémoire du 31 octobre 2008, les époux X._ interjettent un recours en matière civile auprès du Tribunal fédéral. A titre principal, ils reprennent les conclusions formulées en première instance. A titre « alternatif », ils demandent l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité précédente pour nouvelle décision. Des observations n'ont pas été requises.