Question: As a computer programmer I have no problem understanding labels/tags. 

However I find it very hard to make people understand that an email can have more than one label.

Also I find it hard to explain that you can still get to an email if it is not in your inbox and does not have a label.

(Moving a email to a folder seem to be how most people think)

Is gmail just designed by computer programmers for computer programmers? (Hence why I like it so match)

Answer: 
Just tell them that every e-mail is like a movie. The same movie can belong to more than one categories/genres like `comedy`, `action`, `adventure`, etc..
Compared to physical/paper equivalents:

A file folder can contain many documents and you can put a given document in 1. Instead of organizing your document in file folders, you could just stick as many of those small colored post-it notes on them. When you need some document instead of opening a folder, you say "give me all documents with green post-its on them". 

Much better when you're not quite sure in which folder to put a document in, you just stick all relevant post-it colors to the document.