B737NG Captain reported an NMAC occurred at FL350 when a B737 assigned FL340 failed to maintain cleared altitude.

Narrative

We were at 35;000; Air Traffic Control gave us a traffic advisory that Aircraft X was 1;000 feet. below at 340 passing left to right. I spotted the traffic; confirmed the Pilot Flying saw the aircraft and replied to ATC. Immediately ATC started asking Aircraft X if they were level at 340 and they claimed they were. Our TCAS issued a traffic alert and Aircraft X showed 800 feet below us and climbing. RA happened at 600 feet separation! I called out my aircraft disconnected the A/P and complied with TCAS climb. ATC and Aircraft X were arguing their altitude; I think I shouted over everyone Company flight XXXX TCAS climb!!!We received level off at 35.4 and as Aircraft X passed below us I saw red target 400 feet below on TCAS screen. Clear of conflict we returned to 350. I then called back to flight attendants to check on them and passengers. The flight attendants stated the maneuver was barely noticeable and everyone was fine. We continued normal; safe flight to ZZZ and Aircraft X got a phone number for a pilot deviation.