First, exposure is important. You need to be exposed to the sounds and listen to them in natural contexts, over a period of time. Some people will pick up the sounds quicker than others, but you should expect it to take some time. But with continued exposure, you'll notice the differences.
Second, become familiar with articulatory phonetics and read about the phonetics of the language. Don't rely on a pronunciation guide in a beginner's textbook - they are often imprecise. Often the wikipedia page for the language will be OK. See how the phoneme is meant to be pronounced, and try listening for the sounds and see if you can tell the difference.
In my case, I had been learning Korean for several years and pronouncing the [ɾ] phoneme as an English r ([ɹ̠]), without discerning the difference. I knew it wasn't the same, but I could get by. Then I read about the correct phonetic pronunciation, and suddenly I could clearly discern the two sounds.
Third, singing can help. People naturally can enunciate more clearly when singing. First, listen to music in the language and listen for the sounds you are having trouble with. Then try singing the song - trying to pronounce the sounds can be helpful in learning the distinctions.