I tried the following on python 3.5.0a1:

#init.py
__all__ = ['second', 'first']
print('i\'m starting the directory')

#first.py
print('hi, i\'m the first')
from . import second

#second.py
print('hi, i\'m the second')
from . import first

>>> import a.first
i'm starting the directory
hi, i'm the first
hi, i'm the second


it just worked out perfectly, no errors.
But the case I show before still continues to get the AttributeError error.
You told me that basically it doesn't work because it is a circular import, but isn't python already able to manage circular import?
What I expected when running the "from . import *" statament was Python looking up in the __all__ attribute and import everything within it. When it had to import 'first' I expected Python to check in the sys.modules to see if it was already imported so, in this case, it could see that first.py was already imported and no error was raised.