@ml9l: Spontana tanken är att ni bör ha varit kollegor/samarbetat regelbundet under minst ett par månader. Det ser inte lika bra ut om man enbart suttit och, typ, fixat en enstaka bromskloss i projektet.
Personen ska inte bara veta vem du är, utan hur du är. Både som person och som anställd. Detta är en person som ska rekommendera dig, och vara din förkämpe. Man ska inte bara svara på rekryterares frågor, utan i specifika ordalag beskriva varför just du är helt sjukt fantastisk.
Fatta ditt beslut utefter dessa kriterier och förbered din referens, så tror jag inte det kan gå fel.