As an INTJ, I also have horrible memory issues, especially with people. Almost word for word, madhatter explained it. I did some research and read one specific thing that stood out about how to remember things better. It is referred to as using Mnemonic devices, and the particular way I learned is not too difficult:
A new co-worker walks up to you and says "Hi, my name is Josy Ann, how are you today?"
Your first course of action is to repeat her name three times immediately, preferably with the conversation with her. (Yes I know, tedious and irritating, but necessary.)
"Hey Josy Ann, I'm Bill Clinton, it's nice to meet you. I'm doing well. It's Josy Ann you said?"
(People like it if they feel like you really are trying to get to know their name, so being repetitive doesn't actually come off as stupid or otherwise inefficient.)
"Yep, I work in your department now."
"Well that's perfect, we have an cubicle specifically for the next person named Josy Ann right over here."
Whatever, it's done. If you can only say it once or twice, immediately say it out loud once he/she walks away.
NEXT, and here's the really funny part, force your brain to connect those names to an object. Josy sounds (sort of) like a Hose in the shape of a "Z", and Ann sounds sort of like Ants. So think of a Z-shaped hose spraying an ant pile, and repeat "Jo-Z-Ann" to yourself while thinking that.
The POINT of this is NOT to think ridiculous things (although I've read that some people actually DO see those things after using these devices), however to force your brain to make these types of connections. Eventually you will start making these connections easier and easier, and your memory will improve. (I'm still working on mine, and I frequently forget to even try/attempt to make these connections.)
Hope that helped.