Если на коленке делать, то да.
Ну с WCF на C# коммуникационная часть пишется очень быстро и практически сразу работает. В случае если контракт простой и не пытается объять необъятное и засунуть HD видеотелефонию и прочие свистелки и перделки в тот же канал коммуникационная часть пишется за день.
Наверняка и для явы подобные стандартные средства реализаыции веб-сервисов существуют, да и другие кросс-платформенные библиотеки есть.
Более сложной для больших систем является, помоему, проблема скалирования, балансировки нагрузки - как сделать так что бы у миллионов пользователей ничего не тормозило. Тут и база учетных записей пользователе, и бадди списики, оффлайновые сообщения. И самое главное, что бы получать профит нужно все это еще уметь продать, встроить рекламу, в идеальном случае с таргетингом. Ну и еще нужны блэкджек и шлюхи, что бы люди себе его таки установили.
Но все это делается, так что самое сложное: найти того, кто захочет в это дело инвистировать и конкурировать с ICQ, Skype, MSN, AIM и прочими.