Coming back to this old topic, I've got a few more ideas for differentiating these two classes in Basic D&D and similar games like LotFP.
Option 1: "I'm a Magic-User. As in any magic."
Spells are no longer divided into "Cleric" and "Magic-User" lists, but rather "Cleric" and "Elf" lists. If you care about alignment, perhaps the former is Lawful Magic and the latter Chaotic Magic. The Elf class can cast the same spells as before, which is to say the latter list of spells. However, the Magic-User can now learn and cast spells from both lists.
For the Magic-User, "Cleric" spells simply operate as their usual "Elf" spells do in terms of learning, memorization, casting, research, etc. You could either keep the Cleric spells at the same level (e.g. "Bless" remains a first level spell in most systems), or bump them up one level for Magic-Users to give the Cleric class a little more niche protection (e.g. "Bless" remains a first level spell for Clerics, but is a second level spell for Magic-Users).
Magic-Users cannot learn Cleric spells directly from Clerics, because Clerics pray for their spells whereas Magic-Users require written magical formulas to study. Magic-Users can learn Cleric spells randomly at character creation, research them, or copy them from scrolls or the spellbooks of Elves or other Magic-Users. Magic-Users can cast Cleric spells from scrolls, wands, etc., but if your game includes other highly specific magic items that can only be used by certain classes, those class-based restrictions remain.
LotFP-specific details: Magic-Users no longer necessarily need to collaborate with Clerics to make potions of Cleric spells, while Elves still do. Magic-Users are still Chaotic in alignment, because Lawfulness demands a certain degree of so-called "purity." If you have access to VAM and/or EC, then Magic-Users are also capable of Risky Casting, whereas Elves are not.
Option 2: "Fireball? No, I'm not that kind of Elf."
Honestly, I haven't thought this one through nearly as much as Option 1. I just wanted to toss it out there while it was on my mind.
Instead of dividing spells into two lists (one for Clerics and one shared by both Magic-Users and Elves), give each class their own spell list. The Elf represents a third magical tradition alongside the Magic-User and Cleric.* If there is little or no overlap between the Magic-User and Elf lists, and the Magic-Users keeps their usual repertoire, they gain niche protection from Elves and hopefully become more valuable in terms of party balance. The Elves, meanwhile, retain their fighting prowess and unique class abilities, but instead of arguably serving as "Magic-Users-But-Better," they serve an entirely new role as far as spell casting is concerned. Like Clerics, they could work as a sort of mid-point between Fighters and Magic-Users, being skilled in both arms and arcana, but not quite to the level of pure expertise earned by those more focused classes.
The Magic-User memorizes spells from books, learns them individually, and generally casts them empty-handed. The Cleric receives spells through prayer, learns a whole spell level at a time, and casts with a holy symbol. The Elf should have its own quirks. If you've got some house rules for magic you've been itching to try, you could drop them in here. Spell points? Magic Words? Psionics, if you're feeling brave? Bard songs, if you roll that way?
If your system of choice includes "Druid" spells (e.g. BECMI/Rules Cyclopedia D&D, or OD&D + Eldritch Wizardry), you could remove the Druid (sub)class from the game and give its spell list to the Elf. You could also keep the Druid if you want - since Druids can also cast some Cleric spells in the Rules Cyclopedia, you could make them different from Elves by restricting the latter to the new, Druid-based spells. Whether you remove the Druid or not, the Elf might need some additional spells added to the list to flesh it out. If I decide that's a problem, I'm bound to share my solution later.
*Add in two new spell casting classes and give each a thematic color if you want to get all Magic: The Gathering up in here. Heck, if you consider Thief skills to be supernatural in nature, you've got a fourth magic system already.