I can point out one issue that might be affecting things. In your pixel shader function, you are multiplying the red and green values by 256, but you should be multiplying them by 255. The potential values for byte-style colors are not 1-256, they are 0-255. Converting them to a decimal format will work more accurately if you multiply them by 255. Also, taking the average of two colors may not be the best way to go about things. At best, it will allow you to double your potential colors from 256 to 512. But by using the green value as a map to the V axis of the UV coordinates, you could multiply the potential colors instead. Just saying.
Also, I think you may be calculating your UV coordinates incorrectly, as well as unnecessarily. The value you get back from sampling the UV coordinates from the original texture should theoretically be a float value between 0 and 1, so it shouldn't be necessary to alter it any further. I could be wrong about that, but I know it's the way that sampling works in most other shaders I've worked with.
Just a bit of an example. If you were to change your code as little as possible, it would look like this.
float4 outputColor = PaletteTexture.Sample(PaletteTextureSampler, float2((texColor.r + texColor.g) / 2.0, 0.0));
This would add the Red and Green decimal values together, and then divide them by 2 to get the average. The output color float4 is supposed to be four decimal values between 0 and 1, not decimal values between 0 and 255. If you feed it a value above 1, it's going to try to wrap around the texture, and it will be a complete crapshoot as to which part of the texture it will end up sampling. CPUs deal with integer values for colors, so getting a 0 to 255 value makes sense. But GPUs and shaders are all about those floats, and treat colors as 0 to 1 decimals, just like UV coordinates are 0 to 1.