I noticed the same behavior - videos that I converted in HandBrake would play fine on my iPhone, iPod Touch, iPad, and Apple TV, and in iTunes - but they wouldn't play on other computers thru Home Sharing. After an hour of trial and error, I believe I figured it out.
The problem lies in the tagging that is done by HandBrake, as well as Meta-X (which I am using for tagging). Both Meta-X and HandBrake introduce problems with tagging - so here is what I had to do:
1. Convert video via HandBrake
2. Open converted video in Meta-X. You must assign a "type" to the video - in my case, I was converting movies, so I selected "Movie."
3. In the Advanced tab in Meta-X, I had to remove the "Encoding Tool" field. This field gets populated by HandBrake automatically (although HB probably has a setting to ignore this field).
4. Once you save the file in Meta-X, the "Encoding Tool" field will be removed - but the "type" field causes problems.
5. I opened the converted video in Mp3Tag (freeware) and opened the video file with it. Right-clicking on the file, and selecting "Extended Tags," I noticed a tag that was written by Meta-X called "ITUNESMEDIATYPE" - this tag isn't properly handled by Home Sharing in iTunes. I had to remove this tag and save the file with Mp3Tag. All of the other Extended Tags worked fine with Home Sharing - I use GENRE, ITUNEXTC, and TITLE.
After making these changes to each video file, the files played back successfully via iTunes Home Sharing. I'm not sure why these particular tags cause problems - they don't cause problems with other Apple devices, but oh well.
Hope this helps!