THE FLC TAXIED ONTO RWY 23R FOR TKOF WHEN CLRED INTO POS AND HOLD RWY 23L AFTER HOLDING SHORT OF RWY 23L AT CLE. THE ATIS STATED THE ARR RWY WAS RWY 23L AND THE DEPARTING RWY WAS RWY 23R.

Narrative

ATIS INFO AT XA54 (IN PART -- DEP RWY 23R LNDG RWY 23L). COMPLETED ALL DUTIES FOR ENG START AND PUSH BACK. CALLED FOR TAXI INSTRUCTIONS. GND INSTRUCTED #1 FOR TKOF RWY 23R TAXI UP TO HOLD SHORT RWY 23L ON RWY 28. COMPLETED ALL TKOF DUTIES AND BRIEFED FOR RWY 23R DEP. CHANGED TO TWR FREQ. TWR INSTRUCTED POS AND HOLD RWY 23. SHORTLY AFTER WE TAXIED INTO POS AND HOLDING TWR ADVISED US WE WERE ON THE INCORRECT RWY WHICH WAS RWY 23R. WE ASKED IF THERE WAS A CONFLICT AND ADVISED 'NO CONFLICT CLRED FOR TKOF.' ONCE AIRBORNE WE ASKED AGAIN IF ANY PAPERWORK NEEDED TO BE FILED. ADVISED BY TWR AGAIN 'NO HAVE A NICE DAY.' FLT PROCEEDED UNEVENTFULLY TO BWI; WHERE AFTER RELIEF FROM DUTY AND IN CONTACT WITH MY HOME; MY SPOUSE INFORMED ME CLE TWR HAD BEEN IN CONTACT WITH SCHEDULING AND A CALL WAS NEEDED TO CLE TWR. CONTACTED MY CHIEF PLT'S OFFICE THEN PLACED CALL TO CLE TWR; WHERE I WAS ADVISED THERE WAS A PROB AND I SHOULD HAVE BEEN TOLD 'THE MATTER WILL BE INVESTIGATED.' I CONTACTED CHIEF PLT'S OFFICE AGAIN AND MY REPRESENTATIVES. BOTH FO AND I WERE SURE OF OUR INSTRUCTIONS AND HAD BEEN FLYING A 3 DAY TRIP SEQUENCE; WHERE AT NO TIME IF EITHER WAS NOT IN AGREEMENT TO WHAT OUR INSTRUCTIONS WERE; THEY WERE CLARIFIED UNTIL WE WERE BOTH IN AGREEMENT. EVENING BEFORE WAS A REDUCED REST PERIOD. WE FELT CONFIDENT WE COMPLIED WITH ALL INSTRUCTIONS AND CLRNCS; HOWEVER; WE ARE CONCERNED DUE TO MINIMUM REST PERIOD WITH SHORT TIME IN HOTEL. THIS MAY HAVE CONTRIBUTED TO THIS ALLEDGED INCIDENT. CALLBACK CONVERSATION WITH RPTR REVEALED THE FOLLOWING INFO: THE RPTR STATED HE IS THE FIRST PLT IN A LONG TIME AT THIS AIRLINE WHO HAS BEEN UPGRADED TO CAPT IN THE B737-200 AND HAD NEVER BEEN A CAPT BEFORE. WITH THAT IN MIND; HE IS VERY CAREFUL TO WRITE ATIS AND CLRNCS DOWN AND BRIEF AS PER AIRLINE RECOMMENDED PROCS. HE STATED HIS FO AND HE WORK WELL TOGETHER; BUT THE FO HAS A STRONG FOREIGN ACCENT WHICH MAKES HIM DIFFICULT TO UNDERSTAND SOMETIMES. FOR EXAMPLE; THE COPLT IS ACCUSED BY THE ATC SUPVR OF ACKNOWLEDGING CLRNC INTO POS ON RWY 23L; BUT NEITHER THE FO NOR THE CAPT RECALL HIM SAYING THAT AND THE COPLT DID NOT MEAN TO SAY THAT. THE RWY CHANGE WOULD HAVE REQUIRED A NEW BRIEFING IF HE HAD UNDERSTOOD THE RWY WAS CHANGED FROM THE RWY 23R TO RWY 23L BY COMPANY PROC. RWY LENGTHS ARE DIFFERENT AND PWR SETTINGS AND DEP PROCS WOULD HAVE HAD TO BE THOUGHT THROUGH IN THE PROCESS OF ACCOMPLISHING THE BRIEFING. THE CTLR STATED IN A SUBSEQUENT PHONE CONVERSATION THAT HE SHOULD HAVE NOTICED THE FLT TAXIING ON TXWY Z AFTER HE HAD CLRED HIM INTO POS ON RWY 23L.