Is it possible to construct a right triangle with integer sides having both of the legs odd integers?

Hmmm.. my answer is no:

Given a right triangle with sides a, b and c, such that a^2 + b^2 = c^2,
Set a = 2m - 1, and b = 2n - 1 (where m and n are positive integers)

c^2 = a^2 + b^2
c^2 = (4m^2 - 4m + 1) + (4n^2 - 4n + 1)
    = 2(2m^2 + 2n^2 - 2m - 2n + 1)

So c^2 must be even, therefore c must be even.  However, a^2 and b^2 are
odd, so their sum must be odd.  Therefore, there is no such triangle.

-- Glenn Lamb <drofmum@mocten.moc> [Editor: address reversed in the
   original to foil spam scanners]

Well, not quite.  If a^2 and b^2 are odd, then their sum is even.  But,
we can correct the argument by rewriting the last equation as

c^2 = 4(m^2+n^2-m-n)+2

This means that c^2 leaves a remainder of 2 when divided by 4.  But an
even perfect square must be divisible by 4.  Therefore there is no such
triangle.

-- theodore hwa <hwatheod@leland.Stanford.EDU>

That was a stupid mistake I was going to correct just before I read your
post.

In other words, c^2 = 2(2m^2 + 2n^2 - 2m - 2n + 1)
                    = 2*(some odd number)
               so c = sqrt(2)*some odd number
Which rules out c being an integer, pretty much what you said.

-- Glenn Lamb