**Answer: The three denominations are $65$, $72$ and $97$.**

* How did I detect this answer?
I searched the list of primitive Pythagorean triples at [[link to triple list]][1], while using the Frobenius applet available at [[applet link]][2].
Based on my search I know that the answer to the puzzle is unique; still, I would like to see a clean mathematical argument for this (that is not based on enumeration). 

* Even proving that all values from $1000$ onwards are representable is very tedious. I checked $65$ underlying individual cases with a computer program.

* The proof that the value $999$ is not representable is doable. 
Suppose that there exist non-negative integers $x,y,z$ with $65x+72y+97z=999$. 
By considering the equation modulo 9, we get that $x\equiv z \pmod9$.
By considering the equation modulo 2, we get that $x+z$ must be odd.
Since $0\le x\le15$ and $0\le z\le10$, this only leaves a handful of subcases with $x=z+9$ or $z=x+9$; none of these subcases yields an integral value for $y$. 

* I have also found a [[scientific paper]][3] that provides an explicit formula for the Frobenius number of primitive Pythagorean triples:  
$$ F(m^2-n^2, 2mn, m^2+n^2)=(m−1)(m^2−n^2)+(m−1)(2mn)−(m^2+n^2).$$
By setting $m=9$ and $n=4$, we recover the solution $65$, $72$ and $97$ for the Pythagorean coin puzzle as stated above.

  [1]: http://www.math.rutgers.edu/~erowland/tripleslist-long.html
  [2]: http://www.staff.science.uu.nl/~beuke106/frobenius/
  [3]: http://arxiv.org/abs/1402.6440