Это проблема строкового кодирования, которую не следует устранять, заменяя символы вручную, но создавая эти строки с правильной кодировкой в той самой точке, где вы их инициализируете.
Если эти строки взяты из какой-либо базы данных с кодировкой, отличной от UTF-8, вы можете указать эту кодировку для NSString, используя, например:
NSString* string = [NSString stringWithCString: buffer
encoding: NSISOLatin2StringEncoding];
Убедитесь, что понимаете, как источник кодирует строки в первую очередь. Существует много типов строкового кодирования, но iPhone будет поддерживать большинство из них.