1) At least one other person has had this problem, as I saw the problem reported on the Steam forums (
link); that's the only reason I thought to try lowering the graphics options in the first place. I'll add my system specs when I get back on that computer in case it's related to my graphics card or something.
2) I'm not sure what you mean by needing to find the battle tower chest? The problem, as far as I can tell, is that I put my gems in there in the first place. The reason I think so is because of how the sequence of quest messages occurred:
First, I started the quest and got the "New Quest Accepted" message.
Second, I obtained the two malachite gems and got the "Quest Updated" message.
Third, I put the gems in my chest and got the "New Quest Accepted" message again (much like how turning goblin hearts in to Richard causes "New Quest Accepted: Hearttaker" to display again).
Finally, whenever I obtained the gems again (whether by pulling them out of my chest or through some other method, like completing the well quest at High Hall), I didn't get the "Quest Updated" message again, and Simeon failed to recognize that I had them.
This suggests to me that some variable in the game's code failed to reset when the quest was restarted, probably because it wasn't designed with the restart in mind the way Hearttaker is. So for example the game, having already changed the "2 malachite gems in inventory" variable, didn't "think" to check it again as is required for the quest stage to update. This is just a guess on my part, though.
Edit: Just noticed your second message - that's odd. Perhaps it's a difference between the Xbox and PC versions? The only other thing I did differently is to put the gems in the chest directly rather than sending them from the inventory, but I doubt that would make a difference.
Edit2: One other thing I should note is that I was able to complete the quest before putting the malachite gems in the chest (so whatever bug is occurring began at or after that point). I reloaded after doing so because I wanted to get closer to the end of the game and evaluate whether I'd be better off with the malachite or the skill points, but the quest definitely can be completed in my game, even if not in this particular playthrough.