I think there would be a problem if the transformation was almost independent. If one vector were a combination of the others but otherwise there was independence. I think you would have to compute the image of basis to test for this.
If you want to have a high probability for any every black box function it will have to deal with a distribution with either full rank or rank n-1 and that specific case of rank n-1 with no dependent set of rows smaller than n-2 which looks hard.
I have found a paper on randomized algorithms for computing the rank of a matrix here:
www.emis.de/journals/ELA/ela-articles/articles/vol11_pp16-23.ps
