diff --git a/user/src/com/google/gwt/user/rebind/rpc/RemoteServiceAsyncValidator.java b/user/src/com/google/gwt/user/rebind/rpc/RemoteServiceAsyncValidator.java
index 26bc4bc..bb46011 100644
--- a/user/src/com/google/gwt/user/rebind/rpc/RemoteServiceAsyncValidator.java
+++ b/user/src/com/google/gwt/user/rebind/rpc/RemoteServiceAsyncValidator.java
@@ -17,18 +17,18 @@
 
 import com.google.gwt.core.ext.TreeLogger;
 import com.google.gwt.core.ext.UnableToCompleteException;
-import com.google.gwt.core.ext.typeinfo.JArrayType;
 import com.google.gwt.core.ext.typeinfo.JClassType;
 import com.google.gwt.core.ext.typeinfo.JMethod;
 import com.google.gwt.core.ext.typeinfo.JPackage;
 import com.google.gwt.core.ext.typeinfo.JParameter;
-import com.google.gwt.core.ext.typeinfo.JParameterizedType;
 import com.google.gwt.core.ext.typeinfo.JPrimitiveType;
-import com.google.gwt.core.ext.typeinfo.JType;
 import com.google.gwt.core.ext.typeinfo.NotFoundException;
 import com.google.gwt.core.ext.typeinfo.TypeOracle;
 import com.google.gwt.user.client.rpc.AsyncCallback;
 
+import java.util.Map;
+import java.util.TreeMap;
+
 /**
  * Validates the asynchronous version of
  * {@link com.google.gwt.user.client.rpc.RemoteService RemoteService} interface.
@@ -48,7 +48,7 @@
     sb.append(serviceIntf.getSimpleSourceName());
     sb.append("Async {\n");
 
-    JMethod[] methods = serviceIntf.getMethods();
+    JMethod[] methods = serviceIntf.getOverridableMethods();
     for (int index = 0; index < methods.length; ++index) {
       JMethod method = methods[index];
       assert (method != null);
@@ -82,8 +82,8 @@
 
     return sb.toString();
   }
-  private final JClassType asyncCallbackClass;
 
+  private final JClassType asyncCallbackClass;
   private final TypeOracle typeOracle;
 
   RemoteServiceAsyncValidator(TypeOracle typeOracle) throws NotFoundException {
@@ -91,49 +91,58 @@
     asyncCallbackClass = typeOracle.getType(AsyncCallback.class.getName());
   }
 
+  /**
+   * Checks that for there is an asynchronous
+   * {@link com.google.gwt.user.client.rpc.RemoteService RemoteService}
+   * interface and that it has an asynchronous version of every synchronous
+   * method.
+   * 
+   * @throws UnableToCompleteException if the asynchronous
+   *           {@link com.google.gwt.user.client.rpc.RemoteService RemoteService}
+   *           was not found, or if it does not have an asynchronous method
+   *           version of every synchronous one
+   */
   public void validateRemoteServiceAsync(TreeLogger logger,
       JClassType remoteService) throws UnableToCompleteException {
-    logger = logger.branch(TreeLogger.DEBUG,
+    TreeLogger branch = logger.branch(TreeLogger.DEBUG,
         "Checking the synchronous interface '"
             + remoteService.getQualifiedSourceName()
             + "' against its asynchronous version '"
             + remoteService.getQualifiedSourceName() + "Async'", null);
-
-    JClassType remoteServiceAsync = typeOracle.findType(remoteService.getQualifiedSourceName()
-        + "Async");
     boolean failed = false;
-    if (remoteServiceAsync == null) {
-      logger.branch(TreeLogger.ERROR,
+    JClassType serviceAsync = typeOracle.findType(remoteService.getQualifiedSourceName()
+        + "Async");
+    if (serviceAsync == null) {
+      failed = true;
+      branch.branch(TreeLogger.ERROR,
           "Could not find an asynchronous version for the service interface "
               + remoteService.getQualifiedSourceName(), null);
-      failed = true;
     } else {
+      JMethod[] asyncMethods = serviceAsync.getOverridableMethods();
       JMethod[] syncMethods = remoteService.getOverridableMethods();
-      JMethod[] asyncMethods = remoteServiceAsync.getOverridableMethods();
 
-      if (syncMethods.length != asyncMethods.length) {
-        logger.branch(TreeLogger.ERROR, "The asynchronous version of "
+      if (asyncMethods.length != syncMethods.length) {
+        branch.branch(TreeLogger.ERROR, "The asynchronous version of "
             + remoteService.getQualifiedSourceName() + " has "
             + (asyncMethods.length > syncMethods.length ? "more" : "less")
             + " methods than the synchronous version", null);
         failed = true;
       } else {
+        Map asyncMethodMap = initializeAsyncMethodMap(asyncMethods);
         for (int i = 0; i < syncMethods.length; ++i) {
-          JMethod method = syncMethods[i];
-
-          JMethod asyncMethod = remoteServiceAsync.findMethod(method.getName(),
-              getAsyncParamTypes(method));
-
+          JMethod syncMethod = syncMethods[i];
+          String asyncSig = computeAsyncMethodSignature(syncMethod);
+          JMethod asyncMethod = (JMethod) asyncMethodMap.get(asyncSig);
           if (asyncMethod == null) {
-            logger.branch(TreeLogger.ERROR,
+            branch.branch(TreeLogger.ERROR,
                 "Missing asynchronous version of the synchronous method '"
-                    + method.getReadableDeclaration() + "'", null);
+                    + syncMethod.getReadableDeclaration() + "'", null);
             failed = true;
           } else if (asyncMethod.getReturnType() != JPrimitiveType.VOID) {
-            logger.branch(TreeLogger.ERROR,
+            branch.branch(TreeLogger.ERROR,
                 "The asynchronous version of the synchronous method '"
-                    + method.getReadableDeclaration()
-                    + "' must have a void return type", null);
+                    + syncMethod.getReadableDeclaration()
+                    + "' must have a 'void' return type", null);
             failed = true;
           }
         }
@@ -141,44 +150,48 @@
     }
 
     if (failed) {
-      logValidAsyncInterfaceDeclaration(logger, remoteService);
+      logValidAsyncInterfaceDeclaration(branch, remoteService);
       throw new UnableToCompleteException();
     }
   }
 
-  private JType[] getAsyncParamTypes(JMethod method) {
-    JParameter[] params = method.getParameters();
-    JType[] asyncParamTypes = new JType[params.length + 1];
-
-    for (int index = 0; index < params.length; ++index) {
-      asyncParamTypes[index] = getRawType(params[index].getType());
-    }
-
-    asyncParamTypes[params.length] = asyncCallbackClass;
-
-    return asyncParamTypes;
+  private String computeAsyncMethodSignature(JMethod syncMethod) {
+    return computeInternalSignature(syncMethod) + "/"
+        + asyncCallbackClass.getQualifiedSourceName();
   }
 
-  private JType getRawType(JType type) {
-    JParameterizedType parameterized = type.isParameterized();
-    if (parameterized != null) {
-      return getRawType(parameterized.getRawType());
+  private String computeInternalSignature(JMethod method) {
+    StringBuffer sb = new StringBuffer();
+    sb.setLength(0);
+    sb.append(method.getName());
+    JParameter[] params = method.getParameters();
+    for (int j = 0; j < params.length; j++) {
+      JParameter param = params[j];
+      sb.append("/");
+      sb.append(param.getType().getQualifiedSourceName());
     }
+    return sb.toString();
+  }
 
-    JArrayType arrayType = type.isArray();
-    if (arrayType != null) {
-      return typeOracle.getArrayType(getRawType(arrayType.getComponentType()));
+  /**
+   * Builds a map of asynchronous method internal signatures to the
+   * corresponding asynchronous {@link JMethod}.
+   */
+  private Map initializeAsyncMethodMap(JMethod[] asyncMethods) {
+    Map /* <String,JClassType> */sigs = new TreeMap();
+    for (int i = 0; i < asyncMethods.length; ++i) {
+      JMethod asyncMethod = asyncMethods[i];
+      sigs.put(computeInternalSignature(asyncMethod), asyncMethod);
     }
-
-    return type;
+    return sigs;
   }
 
   private void logValidAsyncInterfaceDeclaration(TreeLogger logger,
       JClassType remoteService) {
-    logger = logger.branch(TreeLogger.INFO,
-        "A valid definition for an asynchronous version of interface '"
+    TreeLogger branch = logger.branch(TreeLogger.INFO,
+        "A valid definition for the asynchronous version of interface '"
             + remoteService.getQualifiedSourceName() + "' would be:\n", null);
-    logger.log(TreeLogger.ERROR,
+    branch.log(TreeLogger.ERROR,
         synthesizeAsynchronousInterfaceDefinition(remoteService), null);
   }
 }
\ No newline at end of file
diff --git a/user/src/com/google/gwt/user/rebind/rpc/SerializableTypeOracleBuilder.java b/user/src/com/google/gwt/user/rebind/rpc/SerializableTypeOracleBuilder.java
index d84af23..fa01c3e 100644
--- a/user/src/com/google/gwt/user/rebind/rpc/SerializableTypeOracleBuilder.java
+++ b/user/src/com/google/gwt/user/rebind/rpc/SerializableTypeOracleBuilder.java
@@ -72,11 +72,6 @@
  * <li>Is not default instantiable</li>
  * <li>Has a non-static, non-transient, non-final field whose type is not
  * serializable</li>
- * <li>Has native methods</li>
- * <li>Has a reachable subtype that is not automatically serializable, this
- * error can be treated as a warning if the
- * gwt.allowUnserializableSubtypesOfAutoSerializableTypes property is set to
- * <code>true</code></li>
  * </ul>
  * 
  * <p/> A class qualifies for manual serialization if:
@@ -104,6 +99,10 @@
  * <li>Has native methods</li>
  * <li>Is assignable to {@link Collection} or {@link Map} but it is not a
  * parameterized type</li>
+ * <li>Is automatically serializable and one of its subtypes is not;
+ * this warning can be treated as an error if the
+ * gwt.allowUnserializableSubtypesOfAutoSerializableTypes property is set to
+ * <code>false</code></li>
  * </ul>
  */
 public class SerializableTypeOracleBuilder {
diff --git a/user/test/com/google/gwt/user/client/rpc/InheritanceTest.java b/user/test/com/google/gwt/user/client/rpc/InheritanceTest.java
index e3cccf0..d08d122 100644
--- a/user/test/com/google/gwt/user/client/rpc/InheritanceTest.java
+++ b/user/test/com/google/gwt/user/client/rpc/InheritanceTest.java
@@ -191,7 +191,7 @@
 
   private InheritanceTestServiceAsync getServiceAsync() {
     if (inheritanceTestService == null) {
-      inheritanceTestService = (InheritanceTestServiceAsync) GWT.create(InheritanceTestService.class);
+      inheritanceTestService = (InheritanceTestServiceAsync) GWT.create(InheritanceTestServiceSubtype.class);
       ((ServiceDefTarget) inheritanceTestService).setServiceEntryPoint(GWT.getModuleBaseURL()
           + "inheritance");
     }
diff --git a/user/test/com/google/gwt/user/client/rpc/InheritanceTestServiceSubtype.java b/user/test/com/google/gwt/user/client/rpc/InheritanceTestServiceSubtype.java
new file mode 100644
index 0000000..52fecd2
--- /dev/null
+++ b/user/test/com/google/gwt/user/client/rpc/InheritanceTestServiceSubtype.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2007 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.user.client.rpc;
+
+/**
+ */
+public interface InheritanceTestServiceSubtype extends InheritanceTestService {
+  /**
+   */
+  void foo();
+}
diff --git a/user/test/com/google/gwt/user/client/rpc/InheritanceTestServiceSubtypeAsync.java b/user/test/com/google/gwt/user/client/rpc/InheritanceTestServiceSubtypeAsync.java
new file mode 100644
index 0000000..79ff6aa
--- /dev/null
+++ b/user/test/com/google/gwt/user/client/rpc/InheritanceTestServiceSubtypeAsync.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2007 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.user.client.rpc;
+
+/**
+ * 
+ */
+public interface InheritanceTestServiceSubtypeAsync extends
+    InheritanceTestServiceAsync {
+//  public void foo(AsyncCallback callback);
+}
diff --git a/user/test/com/google/gwt/user/server/rpc/InheritanceTestServiceImpl.java b/user/test/com/google/gwt/user/server/rpc/InheritanceTestServiceImpl.java
index 32c4d35..bba012e 100644
--- a/user/test/com/google/gwt/user/server/rpc/InheritanceTestServiceImpl.java
+++ b/user/test/com/google/gwt/user/server/rpc/InheritanceTestServiceImpl.java
@@ -15,9 +15,9 @@
  */
 package com.google.gwt.user.server.rpc;
 
-import com.google.gwt.user.client.rpc.InheritanceTestService;
 import com.google.gwt.user.client.rpc.InheritanceTestSetFactory;
 import com.google.gwt.user.client.rpc.InheritanceTestSetValidator;
+import com.google.gwt.user.client.rpc.InheritanceTestServiceSubtype;
 import com.google.gwt.user.client.rpc.InheritanceTestSetFactory.AnonymousClassInterface;
 import com.google.gwt.user.client.rpc.InheritanceTestSetFactory.Circle;
 import com.google.gwt.user.client.rpc.InheritanceTestSetFactory.SerializableClass;
@@ -27,7 +27,7 @@
  * TODO: document me.
  */
 public class InheritanceTestServiceImpl extends RemoteServiceServlet implements
-    InheritanceTestService {
+    InheritanceTestServiceSubtype {
 
   public AnonymousClassInterface echo(AnonymousClassInterface serializable) {
     return serializable;
@@ -58,6 +58,9 @@
     return serializableClass;
   }
 
+  public void foo() {
+  }
+
   public SerializableClass getUnserializableClass() {
     return InheritanceTestSetFactory.createNonStaticInnerClass();
   }