In the United States, there is no difference.
Actually, in the United States education is highly decentralized and it is hard to make any generalizations at all. That's probably why Christa's experience is different from mine.
In the United States--in my experience!--"primary school" is often used as a general description of one tier of the educational system. However, the word "primary" is not used as part of the name of any individual school. It is very common for the schools themselves to be named "elementary school:" "Broadmoor Elementary School," "Leopold Higgins Elementary School," etc.
As to why there two names--"primary" and "elementary"--for the same thing, I can't say. These things are matters of history, tradition, and local custom.