Aircraft: GULFSTREAM IV / G350 / G450
Phase of flight: Climb
Anomaly: ATC Issue All Types; Conflict Airborne Conflict

I climbed a G-IV from FL230 to FL350; his final requested altitude was FL450. The G-IV pilot did not speak very clear English but he did read back the correct altitude of FL350. The sector was combined so I had 2 frequencies. Since the G-IV came from the low sector he just happened to be on a different frequency than all the other aircraft. Weather had just started popping up on the RADAR scope and aircraft were starting to ask for deviations. The G-IV was approximately 10 miles south of the CAE VOR heading northbound when he asked for direct FAK and higher. At that time I had a B757 at FL360 that was approximately 5-10 miles northeast of CAE heading southbound. The B757 had asked for deviations to the west for the weather ahead so I advised him he could deviate up to 20 miles right of course and then MILIE Intersection when able. The G-IV asked for direct FAK and higher as he was being stepped on by other aircraft on the other frequency. I gave a G-IV direct FAK and told him I would have higher in 10 minutes (but I meant only 2 minutes). The G-IV acknowledge with direct FAK and OK; and then approximately 1 minute later the B757 said they were responding to a TCAS alert. I then noticed that the G-IV's altitude appeared as though he was climbing. The aircraft were now in the vicinity of CAE where we get erroneous speed readouts on aircraft and sometimes Mode C swaps when aircraft are somewhat close to each other. I asked the G-IV if he was level at FL350 and he did not respond. I can't remember if I asked him twice or not; but once I noticed he had leveled off; he then responded that he was level at FL350. Approximately 4 minutes later the G-IV asked if there was traffic around him and he said he was responding to a TCAS alert. The only other aircraft that was around him was the B757 at FL360 and he told me approximately 6 minutes later that the aircraft below him was showing 400 FT below him and still climbing so they had to respond to their TCAS alert. There was another aircraft in that vicinity but they were at FL240 or FL250 and no factor. I should have changed the G-IV's frequency to the frequency that all the other aircraft were on; but I didn't notice he was on a different frequency until he had asked for direct FAK and higher. I then didn't want to change his frequency because he was so hard to understand and I didn't want to take the chance of him not getting the numbers correct. I also feel that the RADAR site around CAE needs to be checked out if possible. We were level at cruise; FL360; IMC in the tops. We got a TCAS RA; 'climb; climb'. I disconnected the autopilot and initiated a climb. The TCAS quickly changed to 'increase climb; increase climb'; I complied. The First Officer advised ATC that we were in a TCA maneuver climbing. They asked a Gulfstream to say his altitude. He lied. He said he was climbing because he saw us descending into him. He said he saw us go by. We never saw him; but we climbed to 36;800 and he passed 400 FT below us. The TCAS then reported; 'clear of conflict'; we told ATC that we were descending to FL360. I am guessing he blew through his assigned altitude. TCAS saved us. ZJX Controller described a conflict event when an aircraft climbed above cleared altitude; the reporters indicate a language barrier and equipment issues may have contributed to the event.