One major reason may be that it is only known as “acetaminophen” (アセトアミノフェン):
“Paracetamol as it’s known in the Uk has the generic name of acetaminophen. It’s marketed as Tylenol in the US. You can often find Tylenol in regular Japanese pharmacies. If not then ask the doctor for acetaminophen. I’ve been given it in Japan for a fever but it came in 100mg tablets whereas the UK paracetamol is in 500mg tablets. I think the US Tylenol is 350mg in one tablet but I don’t know about the one sold in Japan. Read the label. ”
From the last comment here:
Medicine in Japan on JapanWith Kids
and
“regarding paracetamol I also managed to find it in Japan !
For the people who are unfamiliar with paracetamol it is a very popular drug that is used as a pain reliever (analgesic) and to reduce fever (antipyretic). However it has no anti-inflammatory properties. This drug was first available in the UK in 1956 under the brand name Panadol (“gentle to the stomach”), unlike aspirin this drug didn’t irritate the stomach lining. The name paracetamol was originally the british generic name for the drug but it was later also adopted as the International Non Proprietary Name.
In the US this drug is known as Acetaminophen (a popular brand is Tylenol), it has been available since 1955. In Japan they also call this drug by the US name, Acetaminophen !! So I found that I could buy it at the pharmacy by asking for Acetaminophen ( the dictionary lists this as the katakana pronunciation アセトアミノフェン )
When I asked for paracetamol initially they had never heard of it, or another place told me it wasn’t available in japan. However when I ask for Acetaminophen no problem !”
from near the bottom of here:
Japan Explained FASAQ 
Richard said,
June 30, 2012 at 11:15 am
I discovered this too. Unfortunately, It makes the joke about why there are no aspirin in the jungle even more incomprehensible to Japanese people.
allegorise said,
November 21, 2012 at 1:10 pm
Thank you so much for this advice. After suffering from a splitting headache for two days, I was desperate for paracetamol and had not been able to find it anywhere (I’m pregnant also, just to complicate things). You are a life saver!