If there's any significant (meaning "has any mass") mass in the wallet cover, the phone sees the cover as "your face". Try taking the cover off and see what happens. If it starts working, it's the cover. The proximity sensor is normally on the top "non-screen" edge of the phone, so look there for any appreciable thickness of leather (your skin and leather show as about the same thing). And look for a magnet at the top that keeps the case closed - that can also confuse the sensor.
If not, you need a new proximity sensor. The whole assembly is about $10, the sensor itself is about $6, but the labor is a lot more than a few sensors. The phone has to be opened - and that makes the repair shop liable for any damaged parts they didn't notice.