Just out of curiosty, where did you download the other RPM from? Is it a Mandrake RPM for your distribution?
It also sounds like you need to add more urpmi sources, or add a different one, as usually urpmi works extremely well and will download all dependant rpm's when they are needed. The only times it hasn't installed some software for me is when it doesn't know where to locate the RPM's or they are not available - so I have added more sources and it seems to work.
One of the things I have noticed about the mirrors is that they are not always in sync with each other.
See this post for more information: