Hmm. This may be a bit vague... but then even precision information in Cairo is generally useless. But, for what it's worth:
If you begin at the Midan Talaat Harb (home to the Lialy Hostel), walk West towards the Egyptian Museum along Mahmoud Bassiouni. Turn right at the first street past the "Dahab Hostel" and walk north for about a block and a half. You will see a sort of Art studio on your left and whole bunch of derelict vehicles on your right. In spite of how bad the garage looks, it is secure. I parked there for a month and I was only one of several foreigners to keep a vehicle at that location.
I'll try and get the GPS coordinates for you if you like. (I don't have them, but my friend parked there for two months, and I believe he may still have the digits.)