Message or a type that has MessageContractAttribute and other parameters of different types

No, it means that you have multiple parameters on the method and some of them are not messages. Try posting the interface to your service.

This blog post explains:

... problem is that message contracts cannot be used at the same time as other parameter types. In this case, the return value of the operation is a string. Return values are just another output parameter, so this operation is mixing a message contract message with a primitive parameter type. This fails because message contracts give you control of the layout of the SOAP message, preventing the system from melding in these additional parameters.

Important note:

By the way, the error message you get when you try to mix message contracts looks like this.

This basically means that a particular operation is using a combination of message contract types and primitive types in any of the following combinations:

MixType1: Contract type and primitive types as operation parameters
MixType2: Contract type as a parameter and primitive type as return type
MixType3: Primitive type as a parameter and Contract type as return type

Any of the scenarios listed above would generate the error.

Solved!

I can't return String, I have return Greeting object to the client.

using System;
using System.ServiceModel;
using System.Net.Security;

namespace com.blogspot.jeanjmichel.model
{
    [MessageContract]
    public class Greeting
    {
        private String userGreeting;

        private void SetGreeting()
        {
            DateTime now = DateTime.Now;

            if (now.Hour >= 7 && now.Hour <= 11)
            {
                this.userGreeting = "Good morning";
            }
            else if (now.Hour >= 12 && now.Hour <= 17)
            {
                if (now.Hour == 12 || now.Hour == 13)
                {
                    this.userGreeting = "Good afternoon, it's lunch time!";
                }
                else
                {
                    this.userGreeting = "Good afternoon";
                }
            }
            else if (now.Hour >= 18 && now.Hour <= 20)
            {
                this.userGreeting = "Good evening";
            }
            else
            {
                this.userGreeting = "Good night";
            }
        }

        [MessageBodyMember(Order = 1, ProtectionLevel = ProtectionLevel.EncryptAndSign)]
        public String UserGreeting
        {
            get { return this.userGreeting; }
        }

        public Greeting()
        {
            this.SetGreeting();
        }
    }
}

using System;
using System.ServiceModel;
using com.blogspot.jeanjmichel.model;

namespace com.blogspot.jeanjmichel.services.contract
{
    [ServiceContract(Namespace = "http://jeanjmichel.blogspot.com/services/v0.0.1")]
    public interface IGetGreeting
    {
        [OperationContract]
        Greeting GetGreeting(Credential credential);
    }
}

using System;
using System.ServiceModel;
using com.blogspot.jeanjmichel.services.contract;
using com.blogspot.jeanjmichel.model;

namespace com.blogspot.jeanjmichel.services
{
    [ServiceBehavior(InstanceContextMode = InstanceContextMode.PerCall,
                     Namespace = "http://jeanjmichel.blogspot.com/services/v0.0.1")]
    public class GetGreetingService: IGetGreeting
    {
        public Greeting GetGreeting(Credential credential)
        {
            if (String.IsNullOrEmpty(credential.Token))
            {
                throw new FaultException("Inform the security phrase, and try again.");
            }
            else
            {
                if (credential.Token.Equals("mySeCuriTyP@ss"))
                {
                    Greeting g = new Greeting();
                    return g;
                }
                else
                {
                    throw new FaultException("Wrong password.");
                }
            }
        }
    }
}