Kwonchoba, out of interest, what model android phone have you got?
I'm new to geocaching too (the bug has bitten me, hard), and have been using one of the geocaching apps available on the android marketplace to great effect on my wildfire.
This may be complete bunk, but I'm under the impression that mobile phone GPSrs can be less reliable in terms of signal strength and holding onto the satellites than a proper handheld GPSr. When you fire up your app and are trying to get a GPS lock, make sure you're stood in a nice open area, if possible, with a good clear view of the sky. You haven't said what sort of terrain you're caching in, but I have noticed with mine how much being near or under large trees can affect my signal and my corresponding positioning error. In heavy woodland I've found that I totally lose my GPS signal or when I do have one, end up with a ridiculous positioning error margin. Needless to say I'm already considering getting a proper GPSr for geocaching, I just need to research some recommendations.